Pseudoprime numbers

Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 876 Accepted Submission(s): 358

Problem Description

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

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<math.h>
 4 __int64 sushu(__int64 a)
 5 {
 6     __int64 i;
 7     if(a%2 == 0)
 8     return 0;
 9     for(i = 3; i < sqrt(a); i+=2)
10     {
11         if(a%i == 0)
12         return 0;
13     }
14     return 1;
15 }
16 __int64 ab(__int64 a, __int64 p, __int64 x)//模运算公式
17 {
18     __int64 s;
19     if(p==0)
20     return 1;
21     if(p==1)
22     return a%x;
23     if(p == 2)
24     return (a*a)%x;
25     s=ab(a,p/2,x);
26     if(p%2 == 0)
27     return (s*s)%x;
28     else
29     return (((s*s)%x)*a)%x;
30 
31 }
32 int main()
33 {
34     __int64 p, a, x;
35     while(scanf("%I64d %I64d",&p,&a) != EOF)
36     {
37         if(p==0&&a==0)break;
38         if(sushu(p)==1)
39         printf("no\n");
40         else
41         {
42             x = ab(a,p,p);
43             if(x==a)
44             printf("yes\n");
45             else
46             printf("no\n");
47         }
48     }
49     return 0;
50 }