## 11287 - Pseudoprime Numbers

Moderator: Board moderators

WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:

### 11287 - Pseudoprime Numbers

Could anyone give me some test case? Or tell me where I should be more careful of.

Thanks.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Did you use 64 bit int (i.e long long in C)?
Ami ekhono shopno dekhi...
HomePage

WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:
Yes, I did.

I counted the first 3401 primes(the ones that smaller than 31624), and then checked if p is a prime. If not, then I checked if a^p mod p is equal to a.

This is my function:

Code: Select all

``````long long BigMod(long long a, long long n, long long p)
{
if(n == 1)  return a % p;
else if(n % 2 == 0)  return square(BigMod(a, n/2, p)) % p;
else return square(BigMod(a, n/2, p))*(a % p) % p;
}
long long square(long long k)
{
return k * k;
}
``````
Is there any wrong?

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST
I think u got WA bcoz of integer overflow.
Better u can use this function as Bigmod..

Code: Select all

``````long long Bigmod(long a,long b,long n)
{
long long c=0,d=1,k=0;
long arr[70];
while(b)
{
arr[k++]=b%2;
b/=2;
}
while(k--)
{
c=2*c;
d=(d*d)%n;
if(arr[k]==1)
{
c=c+1;
d=(d*a)%n;
}
}
return d;
}
``````
Hope this helps.

goodwill
New poster
Posts: 25
Joined: Mon Sep 03, 2007 10:54 am
In the case where n is odd, it should be :

Code: Select all

``return (square(BigMod(a, n/2, p))%p)*(a % p) % p; ``

WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:
To mmonish:
Your right. It must be overflow.
I looked your Bigmod. It's a good method, but I don't understand what the use of 'c' in your Bigmod.

To goodwill:
I adapted my BigMod and got accepted.

Thanks to you all.:):)

mmonish
Experienced poster
Posts: 109
Joined: Sun Mar 11, 2007 2:55 pm
Location: SUST
>>WingletE

C can be avoided to compute the Bigmod.
Here c has used to count the current power status.

WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:
Thanks! I got it.

abcman13
New poster
Posts: 6
Joined: Sun Apr 07, 2013 6:00 am

### Re: 11287 - Pseudoprime numbers

hey guys, any suggestions on what i could do to correct my code?

Code: Select all

``````#include <stdio.h>
#include <math.h>

long long int a,p;
int prime[40000],arr[40000];

long long int sq(long long int n);
long long int mod(long long int m);
int isprime();

int main()
{
int l,i,j,k,f;
long long int q;
for(i=3,prime[1]=2,f=2;i<31624;i+=2)
if(arr[i]==0)
{
for(j=i*i,k=2*i;j<31624;j+=k)
arr[j]=1;
prime[f++]=i;
}
prime[f]=1000000001;
while(scanf("%lld %lld", &p,&a)&&p)
{
if(isprime())
{
printf("no\n");
continue;
}
a%=p;
q=mod(p-1)%p;
if(q==1)
printf("yes\n");
else
printf("no\n");
}
return 0;
}

int isprime()
{
int i,l;
if(p<31624)
return !arr[p];
for(i=1,l=(int)sqrt(p)+1;prime[i]<l;i++)
{
if(p%prime[i]==0)
return 0;
}
return 1;
}

long long int sq(long long int n)
{
n%=p;
return (n*n)%p;
}

long long int mod(long long int m)
{
if(m==1)
return a;
if(m%2)
return (a*(sq(mod(m/2))))%p;
return sq(mod(m/2));
}``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11287 - Pseudoprime numbers

Input:

Code: Select all

``````131877361 55808896
0 0
``````
AC output:

Code: Select all

``yes``
Check input and AC output for thousands of problems on uDebug!

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

### Re: 11287 - Pseudoprime Numbers

Hii, I am not getting the required output for uva 11287, Plz help:

Code: Select all

``````#include<cstdio>
#include<cmath>
#include<vector>

using namespace std;
vector<long int> m(31655,1);
long int temp;
long int power(long int a,long int po,long int p)
{
if(p==0)
return 1;
else if(p%2 == 0)
{

temp=(power(a,po,p/2)*power(a,po,p/2))%po;
}
else
{
temp=(power(a,po,(p-1)/2)*power(a,po,(p-1)/2)*a)%po;
}
return temp;
}
int main()
{
long int a,p,u,flag,arr[50],num,k,i,j,mod[10000];
m[0]=m[1]=m[31644]=m[31645]=0;
for(i=2;i<=31655;i++)
{
u=pow(i,0.5);
for(j=2;j<=u;i++)
if(i%j == 0)
{
m[i]=0;
break;
}
}
while(scanf("%ld%ld",&p,&a)!=EOF)
{
if((a==0)&&(p==0))
break;
flag=0;
u=pow(p,0.5);
for(i=2;i<=u;i++)
{
if(m[i])
{
if(p%i==0)
{
flag=1;
break;
}
}
}
if(!flag)
{
printf("no\n");
continue;
}
u=power(a,p,p);
if(u==a)
printf("yes\n");
else
printf("no\n");
}
return 0;
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11287 - Pseudoprime Numbers

It looks like you figured it out.
Check input and AC output for thousands of problems on uDebug!