probable prime
I'm looking for a nice method to test if a arbitrary integer is prime;
of course,I've heard a method named selected method,but now,I find a better way.It is based on the fermat's theorem:if p is prime,any integer a>1,we have a^p=a(mod p);
fermat's theorem gives us a powerful method to test arbitrary positive integer n,choose any integer a,caculate a^(n-1),if n is a prime,then the result must modulo n,if it's not,then the contrary.
btw,there is a quick way to caculate the value of exponentiation,we call it binary exponentiation.I'll introduce it in the next post,maybe with its source code.
of course,I've heard a method named selected method,but now,I find a better way.It is based on the fermat's theorem:if p is prime,any integer a>1,we have a^p=a(mod p);
fermat's theorem gives us a powerful method to test arbitrary positive integer n,choose any integer a,caculate a^(n-1),if n is a prime,then the result must modulo n,if it's not,then the contrary.
btw,there is a quick way to caculate the value of exponentiation,we call it binary exponentiation.I'll introduce it in the next post,maybe with its source code.
posted by sany at 5:55 PM
1 Comments:
ok,the most efficient method to test a positive integer(greater than one)is using sieve.
assume that u want 2 test if n is a prime,then u can list all primes between 2~sqrt(n) first,if any in this list can divide n,then n is composite,if not,the contrary.
it's the first step to solve a basic problem that I've not tackled yet.
Post a Comment
<< Home