Peh, maybe I''ll just sieve it...

I''m doing this for fun, and was interested in any faster prime functions out there. Currently I''m using it to form a prime cloud, I got a huge one working, and I''ll upload the program after I optimize it (need a better prime function) .sen

If you don''t need to be 100% certain wether a number is prime or not, but only need to know with a certain amount of probability you could use a Lehman test. It''s fast, and can practically guarantee a prime. Basically the procedure for testing wether a number p is prime you:
(1) Choose a random number a less than p.
(2) Calculate a to the power of ((p-1)/2) mod p
(3) If that number is not 1 or -1 mod p, then p is definitely
not prime. If it *is* 1 or -1 mod p then the likelyhood that p is not prime is no greater than 50%.

So you run through the test 7 or so times, and if the number passes all times then it is at least 99% certain of being prime.

-Neophyte

-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GED d- s:+ a- C++$ UL++ P++ L++ E W+ N+ o K? w !O M--(+) V-- PS+
PE Y+ PGP t-- 5++ X+ R(+) rv+(++) b+++ DI+ D(+) G e+>++ h r--> y+
----- END GEEK CODE BLOCK-----
geekcode.com

(2) Calculate a to the power of ((p-1)/2) mod p

what exactly were the order of operations here? I am a little confused as to what went first. .sen

(3) If that number is not 1 or -1 mod p, then p is definitely
not prime. If it *is* 1 or -1 mod p then the likelyhood that p is not prime is no greater than 50%.

a little confused there to...

If(n != 1%p && n != -1%p)
Then n is not prime

like that you mean?? .sen

In (2) the order of operations would be
tmp = (p-1)/2
tmp2 = a to the power of tmp (mod p)

For the calculation of tmp2 there are three ways of doing it.
The obvious way, the slow way, and the fast way.
The obvious way would be something like:
tmp2 = pow(a, tmp) % p;

The problem with doing that is that if a or tmp are large numbers you''ll probably get overflow (larger numbers than your variable-types can deal with). Cue the slow way:



The problem with this is that it''s kinda slow.

Cue the fast way:
Well, the fast way of doing powers and mods are kinda long, so I won''t post it here now, but if you''re interested just let me know and I''ll post it.


(3) Technically -1 mod p is the same as p-1, so the test is:
if (n != 1 && n != p-1)
then n is not prime.

Hope that clears it up a little.

-Neophyte

-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GED d- s:+ a- C++$ UL++ P++ L++ E W+ N+ o K? w !O M--(+) V-- PS+
PE Y+ PGP t-- 5++ X+ R(+) rv+(++) b+++ DI+ D(+) G e+>++ h r--> y+
----- END GEEK CODE BLOCK-----
geekcode.com

Thanks! much clearer! I need definite solutions though =(. I implemented a reasonable bit-wise sieve acting on a character array for storage. (8 numbers per byte). It works pretty good, but takes up tons of ram. I was able to generate a prime cloud of primes < 4.29 billion. It looks rather nice and am using a red version of it as my desktop ^_^ .sen

Neophyte :
i''m interested in the fast way !
would you plz post the code ?

thx !

Neophyte : (again)

just checked your "slow" code... doesn''t work for me...

it gives results that differ from

pow (a, ((p-1)/2);

What''s a prime cload?

err... cload=cloud