@ 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 <[email protected]> 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<[email protected]> 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<[email protected]> 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<[email protected]> 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 [email protected].
>>>>>> To unsubscribe from this group, send email to
>>>>>> [email protected].
>>>>>> 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 [email protected].
>>>> To unsubscribe from this group, send email to
>>>> [email protected].
>>>> 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 [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
