素数的队列的计算问题的算法，采用C语言的编程计算实现它

Question

roblem 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

Answer 1

#include <stdio.h>
unsigned long long pow(unsigned long long x, long y,long mod) {
    unsigned long long p = 1;
    while (y) {
        if (y & 1)p = x * p%mod;
        x = x * x%mod;
        y >>= 1;
    }
    return p;
}
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;
}
void main() {
    long p,a;
    while (1) {
        scanf("%ld %ld", &p, &a);
        if (a == 0 || p == 0)break;
        if (!prime(p)&&pow(a,p,p)==a)
            printf("yes\n");
        else
            printf("no\n");
    }
}