Unknown: number of sets

Known: consecutive sequence of ints, each initially in its own set

Conditions: for each set, from any # to another #, we can form a path where the two ends share a prime factor at least P

Insight:

1.for each #, either it has a prime divisor <= sqrt(B) or itself is a prime
2.If two share a prime factor p, then either p <= sqrt(B) or p > sqrt(B)
3.If two share a prime factor p, then the difference of 2 >= p

Subproblem: is it possible for p > sqrt(B)

Answer: 10^6 >= difference of 2 # >= p, but sqrt(B) = 10^6, contradiction!

Therefore, we need to know only primes up to 10^6, and then do something similar to sieve to build numbers bottom up instead of top down, because factoring is hard and slow.

Pseudocode

sieve to 10^6

for each prime p from P to min(10^6, B)
  		factor = A/p + A%p ? 2 : 1

  	
while(p * factor < B) 
	union(p * factor, p * factor -1)
	factor++


for each n from A to B 
	add find(n) to a set

output the size of set

My original implementation can not pass the large dataset, because I used map to store the large number in my union find. Changing map to an array + adding logic to translate large index into a small one solved the problem