prime numbers

udvat · Post by **udvat** » Fri Jul 30, 2004 8:02 pm

say i have to find out whether a=2^31 is prime or not.
but i cant do it by testing if a is divided by the primes between sqrt(a),cause it results in TLE.what should i do then?

is there any efficient method to find primes within a range?can we use seive to find primes in [a,b] ?i mean we should not start seive from 2 but from later numbers.

Alessandro · Post by **Alessandro** » Fri Jul 30, 2004 10:00 pm

For large numbers you can use probabilistic primality testing. This test give result with a certain % of probability to be correct, but with "small" numbers (with less of 500 ciphers, and such numbers aren't big for numbers theorists) it's OK.

But I don't know where you can see the probabilistic primality testing

Friends talked to me about that.

For the primality in the range... you can search the net for sieves. I don't remeber now, but I found a very fast sieve long ago...

Goodbye
Ale

abishek · Post by **abishek** » Fri Jul 30, 2004 10:17 pm

miller rabin test is a very good probablistic test.
fermat's test is also nice, but all the carmichael numbers pass it so it is not used.
you can google for miller rabin and you will find hundreds of results.

well for the theory,

there are elliptic curve based methods that can be used to prove that a number is prime with certainity. also there is the latest algorithm which tests primality in P. but i think those are not for UVA. i haven't even used miller rabin.

if someone finds a sum using miller rabin, kindly point it out. i'd like to try my code.

bye
abi