2019-03-18 16:25

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

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

• 点赞
• 写回答
• 关注问题
• 收藏
• 复制链接分享
• 邀请回答

#### 1条回答

• wudengyu 2年前
``````#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");
}
}
``````
点赞 评论 复制链接分享