@ thanx got it.. silly mistakes ;-) . missed thought it ws + between s and d.
//suggested corrections made.. still not working.. #include<iostream> #include<conio.h> #include<math.h> using namespace std; 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 j,s,d=n-1; while((d&1)==0) d>>=1; s=n/d;for(j=0;1<<j<s;j++); s=j; int primes[6]={2,3,7,31,61,73},i,a,flag; uint64_t x; for(i=0;i<6;i++) { if(primes[i]>=n) break; a=primes[i]; x=uint64_t(pow(a,d))%n; if(x==1 || x==n-1) continue; int r; for(r=1;r<s;r++) { x=(x*x)%n; if(x==1) return 0; if(x==n-1) break; } if(x!=n-1) return 0; } return 1; } main() {for(int k=1;k<2000;k++) if(is_prime(k)) printf("%d is %d\n",k,is_prime(k)); getch(); } On 1/18/12, Terence <technic....@gmail.com> wrote: > @Sourabh > > m=2^s***d > primes[i]*<*n > > > > On 2012-1-18 19:39, Sourabh Singh wrote: >> @Terrence >> >> sry i didn't explain what s,d were they were also wrong i ws >> calculating for n not n-1 >> earlier n=2^s+d >> >> nw m=n-1; for odd n >> m=2^s+d; >> >> //suggested corrections made.. still not working.. >> #include<iostream> >> #include<conio.h> >> #include<math.h> >> using namespace std; >> 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 m=n-1; >> int s,d; >> for(s=0;1<<s<m;++s); s--;d=(m%(1<<s)); >> >> int primes[6]={2,3,7,31,61,73},i,a,flag; >> uint64_t x; >> for(i=0;i<6;i++) >> { if(primes[i]>n) >> break; >> 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; >> if(x==1) >> return 0; >> if(x==n-1) >> break; >> } >> if(x!=n-1) >> return 0; >> } >> return 1; >> } >> main() >> {for(int k=1;k<20;k++) printf("%d is %d\n",k,is_prime(k)); getch();} >> >> >> On 1/18/12, Sourabh Singh<singhsourab...@gmail.com> wrote: >>> @ sunny agrawal >>> >>> you are right. but i have used check a>n also . no improvement . >>> i think algo is wrong in later part.. somewhere.. >>> >>> @ Terence >>> >>> 1) pow may not work for big n but , m just checking for n=1..200 >>> just to check wether algo is right.. and it's not working even for >>> n=7,19... >>> >>> 2) d,s are also coming fine for small values.. of n >>> >>> 3) for x i have used... 64bit integer.. uint64_t in it's declaration. >>> >>> i just want to get algo right first then bother about big n ;-) >>> >>> On 1/18/12, Terence<technic....@gmail.com> wrote: >>>> 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. >>>> >>>> > > -- > 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.