Thread: Fast isPrime() for n < 2^32 View Single Post
2011-05-25, 08:07   #34
JohnFullspeed

May 2011
France

7·23 Posts
speed

Quote:
 Two hours?!? It takes PARI 11 seconds on this machine. (Technically that's "just" to 4.26e9 since this computer is running 32-bit gp.)
sorry my explicatiuon must be wrong

2 hours to compute the first 200 000 000 of primes
so 7200 secondes
7200/200000000= 0,000036 sec by prime
ang 1 000 000 000 of values are tested
7200 / 1000000000= 0,0000072
I don't find It's slow.
You can go faster with a stieve (not Erashotène) but it more hard to programme

I give the time for DIVISION methoid:This method is slow and like you I use an other(Fermat)

It seems that you make a small mistake

If the value has 20 digits and is a primes product
necessary on of the factor is smaller than 2^32
So if you have all the primes smaller 2^32 you are sur th find the other
Liike you have 200 000 000 of primes soif uin fact the value is prime you will make 200 000 000 of divisions.

Let Primes be an array with the 200M of primes

for i:=1 to nb_Primes do
If A mod Primes[ I]=0 then trouve

John