="Warren Smith" <warren.wds@gmail.com> ... We wish to pack the primes into as few bins as possible ... One could try the "first fit decreasing" bin packing heuristic... or others...
I think I eventually decided to not worry about this and just pack them in increasing order, for several (perhaps muddle-headed) reasons: * The smaller primes divide more N, so "greedily" trying 3*5*7*11... first seemed more likely to find a factor sooner. (Your mileage may vary, depending on what your input distribution is like). * Once you get out into the "long tail" of larger primes that are about 1/K of the word size, I didn't see how even with a lot of packing effort one could have much hope to improve significantly over just packing most of them K to a word. * Moreover, since the distribution of sizes is relatively smooth, it didn't seem like the difference between the greedy order and some "optimal" packing would be more than a handful of bins anyway. I now recall however that my goal then was actually to test for primality, rather than find divisors. I think I ultimately wound up doing a small number of GCDs and then siccing Little Fermat on the recalcitrants. I also think I read somewhere in Knuth that Carmichael numbers that fool Fermat have a factor at most cube-root N, so it wasn't necessary to GCD for divisors greater than a third of a word. Back in the day that was ~32 bits, so quite tractable. Today at ~64 bits it might be an interesting exercise for a cloud.