That is not true, there are carmichaels numbers that are 32bit...,
but there is another priamlity testing algorithm, that is log n, and uses
something like fermat therorem, that you can do form 2,3,5 and it works
under 20 000 000.
I dont remeber how the test is done, but maybe it is that you do f
Is there any proof for this ?
On Fri, Jun 27, 2008 at 7:29 AM, Arunachalam wrote:
> What is the maximum value of number that you need to find out?
>
> A 32 bit number is prime if it satisfies the Fermat's theorem for 2,3,5,7
> and 11. This is the fastest way to find out whether a number is prime
There are a few really good randomized algorithms on primality testing.
The AKS algorithm is i guess the best know deterministic primality testing
algo.
On Sat, Jun 28, 2008 at 1:22 PM, Sumedh Sakdeo <[EMAIL PROTECTED]>
wrote:
>
> u can refer this site... its very cool...
> http://www.troubleshoo
u can refer this site... its very cool...
http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm
On 6/27/08, Arunachalam <[EMAIL PROTECTED]> wrote:
> What is the maximum value of number that you need to find out?
>
> A 32 bit number is prime if it satisfies the Fermat's theorem for
What is the maximum value of number that you need to find out?
A 32 bit number is prime if it satisfies the Fermat's theorem for 2,3,5,7
and 11. This is the fastest way to find out whether a number is prime or
not.
regards,
Arunachalam.
On Fri, Jun 27, 2008 at 12:46 AM, rowdy ranga <[EMAIL PROTE
hello sir,
ya it is possible in o(n).dnt worry
first we use a principle of sieve of erasthones
printf("nter no");
scanf("%d",&num);
if((num%2)==0||(num%3)==0||(num%5)==0||(num%7)==0)
printf("notprime");
else
int i=2;
for(;ihttp://groups.google.com/group/algogeeks
-~--~~~~-
You may search at google for the paper "Prime is in P" for a P algorithm.
Note this algorithm is not that fast when given n is small.
On Thu, Jun 19, 2008 at 1:55 PM, zee <[EMAIL PROTECTED]> wrote:
>
> hi everyone ...
>
> any efficient algo to find a number is prime or not ???
>
> (i agree the q