That is Okay but for checking a number n to be prime the chosen values of a
should be less than n according to algorithm
On Wed, Jan 18, 2012 at 3:45 PM, Sourabh Singh <singhsourab...@gmail.com>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.
>
>
--
Sunny Aggrawal
B.Tech. V year,CSI
Indian Institute Of Technology,Roorkee
--
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.
