Thread: Idea for faster sieve View Single Post
2007-06-10, 20:48   #32
Citrix

Jun 2003

110001001112 Posts

Hi Geoff,
Any progress on this. May be you din't understand my last post or there is some confusion on what I wanted.

Just to summarize what I have think will be fastest.

1) From the command line the program gets -x X, and factorizes X. if you want to avoid this step I can enter the factors as -fx a*b*c*d...
2) Then we look at all primes such tht p%X==1. We can use the method below in quotes to generate all such numbers. The only problem is that it will use twice as much memory.
3) Since all numbers are multiples of X and factorization of X is known, we can apply SPH over the entire factorization of X. I plan to use X, such that X>range, so there is no need to check gcd(prime-1,720) etc. Just do SPH over the factorization of X.

Could you please implement this soon. Let me know if you have any questions.

Thanks!

Quote:
 Originally Posted by Citrix 1) then k*N+N*m+1==0 (mod p) where n*m=xand k*N=start 2) To find m we multiply both sides by N' 3) We get k+m+N'==0 (mod p) 4) Solve for m=-(k+N') (mod p) 5) Add p to m till you reach stop and cancel these values as primes.