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 fermat
theorem for (n-1)/2,and so on , but i dont have the book where it is
described...
2009/3/23 Amal <raj.a...@gmail.com>
>
>
> Is there any proof for this ?
>
> On Fri, Jun 27, 2008 at 7:29 AM, Arunachalam <arunachala...@gmail.com>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 or
>> not.
>>
>> regards,
>> Arunachalam.
>>
>> On Fri, Jun 27, 2008 at 12:46 AM, rowdy ranga <aryansmit3...@gmail.com>
>> wrote:
>>
>>>
>>>
>>> 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(;i<num/2;i++)
>>> {
>>> if((num%i)==0)
>>> printf("not prime ");
>>> else printf("prime");
>>>
>>>
>
> >
>
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
