@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.
