Thread: Idea for faster sieve View Single Post
 2007-05-12, 23:49 #7 Citrix     Jun 2003 62516 Posts I analyzed my method further. Code: Looked at the first 2500 primes from 10^15 to...10^15+89353 and found. We can look at 84% of the primes by doing only 30% of the work We can look at 75% of the primes by doing only 17% of the work We can look at 65% of the primes by doing only 12% of the work We can look at 50% of the primes by doing only 7% of the work We can look at 22% of the primes by doing only 1.8% of the work We can look at 4% of the primes by doing only 0.30% of the work Clearly 10% of the factors take almost 2/3 of the time the program runs. I see no point to test these numbers .. now and even later. I think we should only look for the 75% of the factors which can be tested really fast. It would be best to divide sieving into stage 1 and stage2. In stage 1 we can look at only 25% of the primes and find the easy factors first. (upto 2^62) Then we go back in stage 2 and look at the other 50%. No need to look at the remaining 25% or so.. Last fiddled with by Citrix on 2007-05-13 at 00:34