素数的队列的计算问题的算法,采用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个回答

#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");
    }
}
Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
其他相关推荐
C语言求素数算法,有几种方法可以降低时间复杂度

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

c语言编程题目: 回文素数(望解答)

编程任务编号 I: 回文素数(基础版) 时间限制: 1 Sec 内存限制: 64 MB 提交: 1588 解决: 765 [提交][裁判情况] [答疑讨论区] 任务描述 11是一个回文素数.因为它不仅是素数,同时还是回文数(回文数,即把一个数字正着读或者倒着读都是一样的,如121,1331等都是回文数). 现在写一个程序把a的b之间所有的回文素数都找出来(2≤a<b≤1000,000). 输入 第一行,一个整数N(N<10) 以下N行,每行两个整数a,b. 输出 输出回文素数的列表,每行一个,按从小到大的顺序输出. 输入举例 1 5 200 输出举例 5 7 11 101 131 151 181 191

初学者,C语言问题,100-999绝对素数(幻影素数)的问题

绝对素数:例如107和701都是素数,而且他们相反,所以他们是绝对素数。 我会求素数,但是不会求绝对素数,希望大神们能给予帮助啊,不甚感激,希望能在我的代码上补充就好了 ``` #include<stdio.h> int main() { int i,k,flag=1; for(i=100;i<=999;i++) { flag=1;// notice for(k=2;k<i;k++) { if(i%k==0) { flag=0; } } if((flag==1)&&(i!=1)) { printf("%d ",i); } } } ```

实现关于数字的算法问题(c语言)

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

反素数,用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

用C语言实现一个计算100以内质数的程序,要求使用递归实现

用C语言实现一个计算100以内质数的程序,要求使用递归实现

用c语言编程,用筛选法求2到100之间的素数

用筛选法求2到100之间的素数。方法如下:首先2是素数,凡2的倍数都不是素数,于是把这些数从数表中筛去,2以后没有被筛去的第一个数是3,然后把3的倍数都从数表中筛去,3以后没被筛去的第一个数是5,然后把5的倍数都从数表中筛去。如此下去,直到遇到某数K(≤N),其后没有数可筛选为止,这时保留下的未被筛去的数就是2到N的素数。

关于for循环的条件——C语言素数

小白刚学,不是很明白一些问题,代码如下: #include<stdio.h> int main(){ int i,m,n; int sum=0; int cnt=0; scanf("%d %d",&m,&n); if(m==1){ m=2; } for(i=m;i<=n;i++){ int isPrime=1; int k=1; for(k=2;k<i-1;k++){ if(i%k==0){ isPrime=0; break; } } if(isPrime==1){ cnt++; sum+=i; } } printf("%d %d",cnt,sum); return 0; } ---------------------------------------------------- 大致思路是明白,就是越想越乱,for(k=2;k<i-1;k++)这句搞不懂for循环的条件,为什么是k<i-1,debug还是不明白,希望各位能解答一二。另:遇此类for循环条件应该如何去判断,有没有什么简单的实例可以解释一下呢?谢谢!

给定一个区间以内,求其中素数的个数,采用C语言方式的实现

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语言求素数个数,优化方法

以下是题目和我写的代码,但是超时了,谁有更优化的方法吗,求解 /*给定两个非负整数a,b,其中0<= a,b<=1,000,000,请计算这两个数之间有多少个素数。 输入 第一行是一个整数K(1<=K<=1000),表示有多少个样例,每个样例占一行,是两个整数a和b,每个整数之间用一个空格隔开。 输出 每行输出一个样例的结果。 Sample Input 2 2 3 17 19 Sample Output 2 2*/ #include <stdio.h> #include <math.h> int main() { int n,i,j,a,b,sq; scanf("%d",&n); while(n--) { int sum=0; scanf("%d %d",&a,&b); if(a>b) { int temp=a; a=b; b=temp; } for(i=a;i<=b;i++) { sq=sqrt(i); for(j=2;j<=sq;j++) if(i%j==0) break; if(j>sq) sum++; } if(a==1||a==0) sum--; printf("%d\n",sum); } return 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 Hint 2的因子为:1 2 10的因子为:1 2 5 10

用c语言实现素数的判定方法

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

求2到200间的孪生素数(c语言)

尽量用简单的语句,我才开始学从c语言,太复杂了看不懂。求求各位大佬

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语言编程求帮助,

绝对素数是指本身是素数,其逆序数也是素数的数。例如:10321与12301是绝对素数。 编程实现:键盘输入一个整数n,输出小于n的所有绝对素数。 要求:编写函数int isprime(int x)实现测试参数x是否为素数;编写函数int convert(int x),返回参数x的逆序数。main中完成输入输出与函数调用。

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

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

求解C语言编程。。。。。。。

从键盘输入一个整数,输出距离该数最近的素数。根据输入的数不同,此问题可能有一个答案(或者比输入的数大或者比输入的数小),也可能需要输出两个值(一个比输入的数大,一个比输入的数小,两个距离输入的数一样近)。PS:数学意义上的最小素数是2,例如,若输入-213,结果应是2 不要用太高级的字符,新人刚开始学这一块

(C语言)怎样判断大数是否是素数?

输入包含多个测试实例,每个实例包含两行,第一行为整数n,第二行有n个整数(每个整数长度不超过32位,并且每个整数不小于2)。 输出素数的个数。 样例输入: 3 2 3 4 样例输出: 2 这是我写的代码,输入小数据的时候没有问题,数一大就不行了,(因为math.h库里的函数sqrt精度不够,所以又写了一个求平方根函数)。 我听别人说这个题可以用线性筛法写,但我看线性筛法是求一个范围内所有素数的算法呀,跟这题的意思好像不一样,也就没有去用。 这个代码是哪里错了可以改进,还是可以用其他的方法去做,求高人指点!! #include<stdio.h> long long int msqrt(long long int n)//求平方根 { long long int i=0; while(1) { if(i*i<=n) i++; else return i-1; } } long long int prime(long long int n) { if(n==0) return 0; if(n==1) return 0; if(n==2) return 1; if(n==4) return 0; long long int i; for(i=2;i<msqrt(n);i++) { if(n%i==0) return 0; } return 1; } int main() { long long int x,i,n; while(scanf("%lld",&n)!=EOF) { i=0; while(n--) { scanf("%lld",&x); if(prime(x)) i++; } printf("%lld",i); } return 0; }

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的素数,哪里错了 跪求大神指点感激不尽啊啊 啊~~~~~

在中国程序员是青春饭吗?

今年,我也32了 ,为了不给大家误导,咨询了猎头、圈内好友,以及年过35岁的几位老程序员……舍了老脸去揭人家伤疤……希望能给大家以帮助,记得帮我点赞哦。 目录: 你以为的人生 一次又一次的伤害 猎头界的真相 如何应对互联网行业的「中年危机」 一、你以为的人生 刚入行时,拿着傲人的工资,想着好好干,以为我们的人生是这样的: 等真到了那一天,你会发现,你的人生很可能是这样的: ...

删库了,我们一定要跑路吗?

在工作中,我们误删数据或者数据库,我们一定需要跑路吗?我看未必,程序员一定要学会自救,神不知鬼不觉的将数据找回。 在 mysql 数据库中,我们知道 binlog 日志记录了我们对数据库的所有操作,所以 binlog 日志就是我们自救的利器。 接下来就来开启程序员自救之路。 想要自救成功,binlog 这把利器一定要好,在自己之前,我们一定要确定我们有 binlog 这把利器,以下就是确保有 bi...

再不跳槽,应届毕业生拿的都比我多了!

跳槽几乎是每个人职业生涯的一部分,很多HR说“三年两跳”已经是一个跳槽频繁与否的阈值了,可为什么市面上有很多程序员不到一年就跳槽呢?他们不担心影响履历吗? PayScale之前发布的**《员工最短任期公司排行榜》中,两家码农大厂Amazon和Google**,以1年和1.1年的员工任期中位数分列第二、第四名。 PayScale:员工最短任期公司排行榜 意外的是,任期中位数极小的这两家公司,薪资...

我以为我学懂了数据结构,直到看了这个导图才发现,我错了

数据结构与算法思维导图

技术大佬:我去,你写的 switch 语句也太老土了吧

昨天早上通过远程的方式 review 了两名新来同事的代码,大部分代码都写得很漂亮,严谨的同时注释也很到位,这令我非常满意。但当我看到他们当中有一个人写的 switch 语句时,还是忍不住破口大骂:“我擦,小王,你丫写的 switch 语句也太老土了吧!” 来看看小王写的代码吧,看完不要骂我装逼啊。 private static String createPlayer(PlayerTypes p...

华为初面+综合面试(Java技术面)附上面试题

华为面试整体流程大致分为笔试,性格测试,面试,综合面试,回学校等结果。笔试来说,华为的难度较中等,选择题难度和网易腾讯差不多。最后的代码题,相比下来就简单很多,一共3道题目,前2题很容易就AC,题目已经记不太清楚,不过难度确实不大。最后一题最后提交的代码过了75%的样例,一直没有发现剩下的25%可能存在什么坑。 笔试部分太久远,我就不怎么回忆了。直接将面试。 面试 如果说腾讯的面试是挥金如土...

和黑客斗争的 6 天!

互联网公司工作,很难避免不和黑客们打交道,我呆过的两家互联网公司,几乎每月每天每分钟都有黑客在公司网站上扫描。有的是寻找 Sql 注入的缺口,有的是寻找线上服务器可能存在的漏洞,大部分都...

讲一个程序员如何副业月赚三万的真实故事

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

上班一个月,后悔当初着急入职的选择了

最近有个老铁,告诉我说,上班一个月,后悔当初着急入职现在公司了。他之前在美图做手机研发,今年美图那边今年也有一波组织优化调整,他是其中一个,在协商离职后,当时捉急找工作上班,因为有房贷供着,不能没有收入来源。所以匆忙选了一家公司,实际上是一个大型外包公司,主要派遣给其他手机厂商做外包项目。**当时承诺待遇还不错,所以就立马入职去上班了。但是后面入职后,发现薪酬待遇这块并不是HR所说那样,那个HR自...

女程序员,为什么比男程序员少???

昨天看到一档综艺节目,讨论了两个话题:(1)中国学生的数学成绩,平均下来看,会比国外好?为什么?(2)男生的数学成绩,平均下来看,会比女生好?为什么?同时,我又联想到了一个技术圈经常讨...

副业收入是我做程序媛的3倍,工作外的B面人生是怎样的?

提到“程序员”,多数人脑海里首先想到的大约是:为人木讷、薪水超高、工作枯燥…… 然而,当离开工作岗位,撕去层层标签,脱下“程序员”这身外套,有的人生动又有趣,马上展现出了完全不同的A/B面人生! 不论是简单的爱好,还是正经的副业,他们都干得同样出色。偶尔,还能和程序员的特质结合,产生奇妙的“化学反应”。 @Charlotte:平日素颜示人,周末美妆博主 大家都以为程序媛也个个不修边幅,但我们也许...

MySQL数据库面试题(2020最新版)

文章目录数据库基础知识为什么要使用数据库什么是SQL?什么是MySQL?数据库三大范式是什么mysql有关权限的表都有哪几个MySQL的binlog有有几种录入格式?分别有什么区别?数据类型mysql有哪些数据类型引擎MySQL存储引擎MyISAM与InnoDB区别MyISAM索引与InnoDB索引的区别?InnoDB引擎的4大特性存储引擎选择索引什么是索引?索引有哪些优缺点?索引使用场景(重点)...

如果你是老板,你会不会踢了这样的员工?

有个好朋友ZS,是技术总监,昨天问我:“有一个老下属,跟了我很多年,做事勤勤恳恳,主动性也很好。但随着公司的发展,他的进步速度,跟不上团队的步伐了,有点...

我入职阿里后,才知道原来简历这么写

私下里,有不少读者问我:“二哥,如何才能写出一份专业的技术简历呢?我总感觉自己写的简历太烂了,所以投了无数份,都石沉大海了。”说实话,我自己好多年没有写过简历了,但我认识的一个同行,他在阿里,给我说了一些他当年写简历的方法论,我感觉太牛逼了,实在是忍不住,就分享了出来,希望能够帮助到你。 01、简历的本质 作为简历的撰写者,你必须要搞清楚一点,简历的本质是什么,它就是为了来销售你的价值主张的。往深...

外包程序员的幸福生活

今天给你们讲述一个外包程序员的幸福生活。男主是Z哥,不是在外包公司上班的那种,是一名自由职业者,接外包项目自己干。接下来讲的都是真人真事。 先给大家介绍一下男主,Z哥,老程序员,是我十多年前的老同事,技术大牛,当过CTO,也创过业。因为我俩都爱好喝酒、踢球,再加上住的距离不算远,所以一直也断断续续的联系着,我对Z哥的状况也有大概了解。 Z哥几年前创业失败,后来他开始干起了外包,利用自己的技术能...

现代的 “Hello, World”,可不仅仅是几行代码而已

作者 |Charles R. Martin译者 | 弯月,责编 | 夕颜头图 |付费下载自视觉中国出品 | CSDN(ID:CSDNnews)新手...

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

如果世界上都是这种不思进取的软件公司,那别说大部分程序员只会写 3 年代码,恐怕就没有程序员这种职业。

离职半年了,老东家又发 offer,回不回?

有小伙伴问松哥这个问题,他在上海某公司,在离职了几个月后,前公司的领导联系到他,希望他能够返聘回去,他很纠结要不要回去? 俗话说好马不吃回头草,但是这个小伙伴既然感到纠结了,我觉得至少说明了两个问题:1.曾经的公司还不错;2.现在的日子也不是很如意。否则应该就不会纠结了。 老实说,松哥之前也有过类似的经历,今天就来和小伙伴们聊聊回头草到底吃不吃。 首先一个基本观点,就是离职了也没必要和老东家弄的苦...

HTTP与HTTPS的区别

面试官问HTTP与HTTPS的区别,我这样回答让他竖起大拇指!

程序员毕业去大公司好还是小公司好?

虽然大公司并不是人人都能进,但我仍建议还未毕业的同学,尽力地通过校招向大公司挤,但凡挤进去,你这一生会容易很多。 大公司哪里好?没能进大公司怎么办?答案都在这里了,记得帮我点赞哦。 目录: 技术氛围 内部晋升与跳槽 啥也没学会,公司倒闭了? 不同的人脉圈,注定会有不同的结果 没能去大厂怎么办? 一、技术氛围 纵观整个程序员技术领域,哪个在行业有所名气的大牛,不是在大厂? 而且众所...

男生更看重女生的身材脸蛋,还是思想?

往往,我们看不进去大段大段的逻辑。深刻的哲理,往往短而精悍,一阵见血。问:产品经理挺漂亮的,有点心动,但不知道合不合得来。男生更看重女生的身材脸蛋,还是...

程序员为什么千万不要瞎努力?

本文作者用对比非常鲜明的两个开发团队的故事,讲解了敏捷开发之道 —— 如果你的团队缺乏统一标准的环境,那么即使勤劳努力,不仅会极其耗时而且成果甚微,使用...

为什么程序员做外包会被瞧不起?

二哥,有个事想询问下您的意见,您觉得应届生值得去外包吗?公司虽然挺大的,中xx,但待遇感觉挺低,马上要报到,挺纠结的。

当HR压你价,说你只值7K,你该怎么回答?

当HR压你价,说你只值7K时,你可以流畅地回答,记住,是流畅,不能犹豫。 礼貌地说:“7K是吗?了解了。嗯~其实我对贵司的面试官印象很好。只不过,现在我的手头上已经有一份11K的offer。来面试,主要也是自己对贵司挺有兴趣的,所以过来看看……”(未完) 这段话主要是陪HR互诈的同时,从公司兴趣,公司职员印象上,都给予对方正面的肯定,既能提升HR的好感度,又能让谈判气氛融洽,为后面的发挥留足空间。...

面试阿里p7,被按在地上摩擦,鬼知道我经历了什么?

面试阿里p7被问到的问题(当时我只知道第一个):@Conditional是做什么的?@Conditional多个条件是什么逻辑关系?条件判断在什么时候执...

终于懂了TCP和UDP协议区别

终于懂了TCP和UDP协议区别

无代码时代来临,程序员如何保住饭碗?

编程语言层出不穷,从最初的机器语言到如今2500种以上的高级语言,程序员们大呼“学到头秃”。程序员一边面临编程语言不断推陈出新,一边面临由于许多代码已存在,程序员编写新应用程序时存在重复“搬砖”的现象。 无代码/低代码编程应运而生。无代码/低代码是一种创建应用的方法,它可以让开发者使用最少的编码知识来快速开发应用程序。开发者通过图形界面中,可视化建模来组装和配置应用程序。这样一来,开发者直...

面试了一个 31 岁程序员,让我有所触动,30岁以上的程序员该何去何从?

最近面试了一个31岁8年经验的程序猿,让我有点感慨,大龄程序猿该何去何从。

大三实习生,字节跳动面经分享,已拿Offer

说实话,自己的算法,我一个不会,太难了吧

程序员垃圾简历长什么样?

已经连续五年参加大厂校招、社招的技术面试工作,简历看的不下于万份 这篇文章会用实例告诉你,什么是差的程序员简历! 疫情快要结束了,各个公司也都开始春招了,作为即将红遍大江南北的新晋UP主,那当然要为小伙伴们做点事(手动狗头)。 就在公众号里公开征简历,义务帮大家看,并一一点评。《启舰:春招在即,义务帮大家看看简历吧》 一石激起千层浪,三天收到两百多封简历。 花光了两个星期的所有空闲时...

立即提问
相关内容推荐