POJ3641:Pseudoprime numbers

Description Fermat's theorem states that for any prime number p and for any integer a > 1, ap = 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 ≤ 1000000000 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   [cpp]      [cpp]   #include   using namespace std;      int prime(long long a)   {       int i;       if(a == 2)           return 1;       for(i = 2; i*i<=a; i++)           if(a%i == 0)               return 0;       return 1;   }      long long mod(long long a,long long b,long long m)   {       long long ans = 1;       while(b>0)       {           if(b&1)           {               ans = ans*a%m;               //b--;           }           b>>=1;           a = a*a%m;       }       return ans;   }      int main()   {       long long a,p;          while(cin >> p >> a && (p||a))       {           long long ans;           if(prime(p))           cout << "no" << endl;           else           {               ans = mod(a,p,p);               if(ans == a)               cout << "yes" << endl;               else               cout << "no" << endl;           }       }          return 0;   }