http://groups.google.com/group/google-code/browse_thread/thread/8d515e0cd122b5cc/c4e31576703edfe3#c4e31576703edfe3

The key idea is to realize that you will end up with two
kinds of sets:

a) those containing a single element
b) those which are the union of sets of cardinality >= 2 of the form
{multiples of a prime}

Consider sets of type b first. In order for p to have two multiples
between a and b, p must be <= b-a. Since b-a < 1000000, we'll need the
prime numbers less than a million; easiest is to download these off
the internet.

(We can use the Implicit Heap method from http://www.haskell.org/haskellwiki/Prime_numbers#Implicit_Heap.
 Basically, takeWhile (<=10^6) primes. )

Now for any two primes p, q, their multiples will end up in the same
set of type b if there is a number between a and b that is a multiple
of pq. Thus, as suggested by Jelani,
1) start with each prime P <= p <= b-a in its own set
2) for each pair of such primes, union their sets if a % pq = 0 or a -
(a % pq) + pq < b.
Use union-find data structures to make the above efficient.

The resulting sets are all of the sets of type b. To find the sets of
type a, use a Sieve of Erastophanes-type approach: write down the
numbers from a to b, iterate over every prime in the sets just
computed, and cross off every multiple of that prime between a and b.
Each number left will be a single-element set of type a.