1. the computing of d is incorrect.
d = n-1;
while((d&1)==0) d>>=1;
2. the accuracy of pow is far from enough. you should implement your own
pow-modulo-n method.
3. for big n, (exceed 32bit), x=(x*x)%n can be overflow also. you may
need to implement your own multiply method in this case.
On 2012-1-18 18:15, Sourabh Singh wrote:
@all output's to above code are just random.. some prime's. found
correctly while some are not
why i used certain primes to check ie.(2,3,31,73,61,7) coz.. its given
n wiki for about 10^15 checking with these is enough..
On 1/18/12, Sourabh Singh<singhsourab...@gmail.com> wrote:
@ALL hi everyone m trying to make prime checker based on miller-rabin
test . can some1 point out . wat's wrong with the code. thank's alot
in advance...
//prime checker based on miller-rabin test
#include<iostream>
#include<conio.h>
#include<math.h>
int is_prime(int n)
{
if(n==2 | n==3)
return 1;
if(((n-1)%6!=0& (n+1)%6!=0) || n<2)
return 0;
int s,d;
for(s=0;1<<s<n;++s); s--;d=(n%(1<<s));
int primes[6]={2,3,7,31,61,73},i,a,flag;
uint64_t x;
for(i=0;i<6;i++)
{ flag=0;
a=primes[i];
x=uint64_t(pow(a,d))%n;
if(x==1 | x==n-1)
continue;
for(int r=1;r<s;r++)
{ x=(x*x)%n;
printf("x is %llu\n",x);
if(x==1)
return 0;
else
flag=1;
}
if(flag)
continue;
return 0;
}
return 1;
}
main()
{
for(int k=1;k<100;k++)
{
printf("%d is %d\n",k,is_prime(k));
}
getch();
}
--
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?hl=en.
--
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?hl=en.
