2506: Pseudoprime numbers

Fermat's theorem states that for any prime number p and for any integer a > 1, a^p == a (mod p). That is, if we raise a to the pth power and divide by p, the remainder is a. Some (but not very many) non-prime values of p, known as base-a pseudoprimes, have this property for some a. (And some, known as Carmichael Numbers, are base-a pseudoprimes for all a.) Given 2 < p ≤ 1,000,000,000 and 1 < a < p, determine whether or not p is a base-a pseudoprime.

Input

Input contains several test cases followed by a line containing "0 0". Each test case consists of a line containing p and a.

Output

For each test case, output "yes" if p is a base-a pseudoprime; otherwise output "no".

Sample Input

3 2
10 3
341 2
341 3
1105 2
1105 3
0 0

Sample Output

no
no
yes
no
yes
yes

#include<iostream>
#include<math.h>
using namespace std;
long long mod(int b,int p,int m)
{
 if(p==0) return 1;
 if(p%2) return (b%m*mod(b,p-1,m))%m;
 long long temp=mod(b,p/2,m);
 return (temp*temp)%m;
}
int main()
{
 long long a,p;
 while(cin>>p>>a&&a&&p)
 {
  //cout<<a<<"   "<<mod(a,p,p)<<endl;
  int flag=1,i;
  double l=sqrt(p*1.0);
  for(i=2;i<=l;i++) if(p%i==0) {flag=0;break;}
  if(flag) {printf("no/n");continue;}
  //cout<<mod(a,p,p)<<"    "<<a<<endl;
  if(mod(a,p,p)==a) printf("yes/n");
  else printf("no/n");
 }
 return 0;
}
  
/*  

#include<stdio.h>
 long mod(int b,int p,int m)
{
 if(m==1||b==0) return 0;
 if(p==0) return 1;
 if(p%2) return (b%m*mod(b,p-1,m))%m;
 long long temp=mod(b,p/2,m);
 return (temp*temp)%m;
}
int main()
{
 long long b,p,m;
 while(scanf("%ld%ld",&b,&p)!=-1)
 {
  printf("%ld/n",mod(b,p,p));
 }
 return 0;
}

*/