I also thought of storing the factors in a Hashmap for each location, to avoid the trial division.
But even storing even one (the highest) factor increases the sieving stage so dramatically (factor 2) that it is slower then the version with the complete trial division stage. In my implementation trial division has the same running time as sieving.
Only storing the highest factor uses just another array. Storing all factors uses much more resources (Hashmap or array) and time.
|