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个回答

``````#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");
}
}
``````

C语言求素数算法，有几种方法可以降低时间复杂度

b可以非常大的时候，输出a到b之间素数的个数，怎么才能简化算法，降低运行时间

c语言编程题目： 回文素数（望解答）

# c语言实现 输入若干个正整数， 从输入的若干个数字中选择一部分数字出来(可以全部选择)， 将选择的数字分成n组，每组数字的个数可以不一样， 但要求每组数字的和相等并且尽可能最大！ 如果可以实现则输出最大和，如果无法完成则输出0

Problem Description 反素数就是满足对于任意i(0<i<x),都有g(i)<g(x),(g(x)是x的因子个数),则x为一个反素数。现在给你一个整数区间[a,b],请你求出该区间的x使g(x)最大。 Input 第一行输入n,接下来n行测试数据 输入包括a,b, 1<=a<=b<=5000,表示闭区间[a,b]. Output 输出为一个整数,为该区间因子最多的数.如果满足条件有多个,则输出其中最小的数. Sample Input 3 2 3 1 10 47 359 Sample Output 2 6 240

Problem Description Easy question! Calculate how many primes between [1...n]! Input Each line contain one integer n(1 <= n <= 1e11).Process to end of file. Output For each case, output the number of primes in interval [1...n] Sample Input 2 3 10 Sample Output 1 2 4

c语言求素数个数，优化方法

Problem Description 反素数就是满足对于任意i(0<i<x),都有g(i)<g(x),(g(x)是x的因子个数),则x为一个反素数。现在给你一个整数区间[a,b],请你求出该区间的x使g(x)最大。 Input 第一行输入n,接下来n行测试数据 输入包括a,b, 1<=a<=b<=5000,表示闭区间[a,b]. Output 输出为一个整数,为该区间因子最多的数.如果满足条件有多个,则输出其中最小的数. Sample Input 3 2 3 1 10 47 359 Sample Output 2 6 240 Hint 2的因子为：1 2 10的因子为:1 2 5 10

Problem Description 对于表达式n^2+n+41，当n在（x,y）范围内取整数值时（包括x,y）(-39<=x<y<=50)，判定该表达式的值是否都为素数。 Input 输入数据有多组，每组占一行，由两个整数x，y组成，当x=0,y=0时，表示输入结束，该行不做处理。 Output 对于每个给定范围内的取值，如果表达式的值都为素数，则输出"OK",否则请输出“Sorry”,每组输出占一行。 Sample Input 0 1 0 0 Sample Output OK

c语言,编程,不知道哪里错了,感觉没错....

![图片说明](https://img-ask.csdn.net/upload/201903/31/1554026314_842666.png) 这个代码是错误的,我只是想输入一个数字,然后提示是不是素数而已,现在出错了,我没有看懂错在哪里,大神指点下 ----------------------------------------------- 现在可以了，已经解决 ``` #include<stdio.h> int ok_or_no(int a) { int i; if(a==2) { return 0; } a=(int)a/2+1; for(i=2;i<a;i++) { if(a%i==0) { return 1; } } if(a>1) return 0; else return 1; } int main() { int even_my=0; scanf("%d",&even_my); if(ok_or_no(even_my)) { printf("%s","这不是个素数\n"); } else { printf("%s","这是个素数\n"); } return 0; } ``` ```

C语言计算1000以内的质数的和，并且输出出来，代码

C 语言计算1000以内的质数的和，并且输出出来，代码怎么来写

（C语言）怎样判断大数是否是素数？

c语言打印素数程序求大神

#include<stdio.h> int main() { int a[101],i,j; for(i=0;i<101;i++) a[i]=i; for(i=0;i<101;i++) { for(j=0;j<i-1;j++) { if(a[i]%j!=0)break; } a[i]=0; } for(i=0;i<101;i++) if(a[i]=0) printf("%d is a sushu.",i); return 0; } 初学者啊啊啊啥都不会，打印1-100的素数，哪里错了 跪求大神指点感激不尽啊啊 啊~~~~~

loonggg读完需要3分钟速读仅需 1 分钟大家好，我是你们的校长。我之前讲过，这年头，只要肯动脑，肯行动，程序员凭借自己的技术，赚钱的方式还是有很多种的。仅仅靠在公司出卖自己的劳动时...

MySQL数据库面试题（2020最新版）

!大部分程序员只会写3年代码

HTTP与HTTPS的区别