View Single Post
Old 2005-12-06, 14:41   #10
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

1438 Posts
Default

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.
ThiloHarich is offline   Reply With Quote