Re: [PrimeNumbers] Coprimes Puzzle
- Phil Carmody wrote:
> i=0;ps=0;pr=1;pend=1;p=1;while(p<400000000,i++;p=nextprime(p+1);A simple optimisation follows from your post:
> ps+=p;if(i%10000==0,print(i" "p));f=factor(ps);l=length(f~);
> print(i" "p" "ps" "factor(ps)" "g)),pend*=p))
If gcd(pr+1,ps)>1 then gcd(pr+1,ps) must be f[l,1] (the largest
prime factor of ps).
So gcd(pr+1,ps)>1 can be replaced by the faster (pr+1)%f[l,1]==0.
In my timings, using pr%f[l,1]==f[l,1]-1 was a few percent faster than
I have tested to n=1000000, p=15485863 with no new solution.
> (The optimisation of only performing the * and % when there'sYes, a tree-sieve should make it much faster but I'm not spending time
> possible factor did save a small amount of time. This technique
> might be amenable to a tree-sieve and fewer bigger multiplies. Jens?)
Jens Kruse Andersen