View Single Post
Old 2007-05-12, 23:49   #7
Citrix
 
Citrix's Avatar
 
Jun 2003

62516 Posts
Default

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