I have a set of numbers, all positive, integers obviously, and what I want to do is divide them in the least possible groups with each group having a GCD bigger than 1. The biggest possible number is 2^64-1. What I also need to do is keep the complexity as low as possible. I am aware that there are a lot of prime numbers from 0 to 2^64-1 but each of those will be in its own group containing only one number. Any thoughts?
Break a set of numbers to minimum groups with each having a common divider
optimization
If your set of numbers contains any number from 1 to $N$, then the answer is pretty obvious: You will need $\pi(N)+1$ groups where $\pi(N)$ is the number of primes less than or equal to $N$. That is because each of the $\pi(N)$ primes as well as 1 can not go into the same group as any of the others as they have no common divider. The remaining numbers, however, are obviously multiples of one of the primes, and you can for example put it into the group of its smallest divider. The optimal complexity algorithm to group everything is to use the sieve of Eratosthenes:Put 1 in its own groupPut all multiples of 2 from 2 to $N$ into one groupPut all multiples of 3 from 3 to $N$ that have not previously been put into a group, into their own groupSince you have already handled 4, skip itPut all multiples of 5 from 5 to $N$ that have not previously been put into a group, into their own groupSince you have already handled 6, skip itPut all multiples of 7 from 7 to $N$ that have not previously been put into a group, into their own groupEtc.The situation is more complicated if you have a set of numbers that is not complete. But a variation of the sieve algorithm above should still be able to do the job.