素数c语言|c语言如何输出1到100所有素数思路
问:1-100之间有多少个素数,并输出所有素数及素数的个数。
这个题面就很容易理解了,数学上对素数的定义是这样的:质数又称素数,指在一个大于1的自然数中,除了1和此整数自身外,没法被其他自然数整除的数。
换句话说,只有两个正因数(1和自己)的自然数即为素数。比1大但不是素数的数称为合数。并且1和0既非素数也非合数。
好了,数学上素数是这样定义,我们应该把它用计算机的语言表示出来呀。
这里我们就用一种最简单的方式来表示:
编程思想:一个数n,要判断它是不是素数,直接用n除以2到n里面所有的数,如果有一个能整除,则这个数n不是素数。如果都不能被整除,则这个数是素数。
上面这句话用代码写出来是这样的:
for(j = 2; j<= n; j ) //能被2到n整除的数
{
if(i % j == 0) //取余判断
{
flag = 0;
break;
//只要有一个被整除,则跳出循环
}
}
到这里,我们仔细想想,有必要一直除到n去吗?答案是没有必要的,来看一个例子。
比如判断17是不是素数,我们其实只需要计算:
17%2
17%3
17%4
只需要计算以上三个式子,我们就可以断定,17是一个素数。
为什么呢?因为数学知识告诉我们:任何一个数都不可能分解成两个大于其平方根的数的乘积呀,肯定只能分解为一个大于或等于其平方根,另一个小于或等于其平方根的两个数相乘。
我们知道,17开根号的值是一个4到5之间的数,取int之后就是4,既然我们已经从2一直取余取到了4都没有一个可以整除,那么就没有必要继续计算下去了,因为接下来的数也肯定不能被整除。
我们吧代码优化一下:
for(j = 2; j<= sqrt(n); j ) //能被2到n的开方根整除的数
{
if(i % j == 0)
{
flag = 0;
break;
}
}
好了,这样子你能明显感受到我们一下子减少了很多计算量,时间复杂度降低了。
完整代码以上是知道一个数,判断它是不是素数,这里我们要做的是输出1-100内所有的素数,那么就要有一个双重for循环,一个数一个数地去判断,然后输出素数。
这里给出完整代码:
//输出1-100的所有素数
void Prime()
{
int i,j,flag,n;
n = 100; //100以内的素数
flag = 1; //标识变量,是素数则为1
for(i = 2; i <= 100; i ) //从2开始,遍历到100
{
flag = 1;
for(j = 2; j*j <= i; j ) //能被2 - sqrt(i)整除的数
{
if(i % j == 0)
{
flag = 0;
break;
}
}
if(flag == 1)
printf("%d ",i); //输出素数
}
}
与素数有关的猜想关于求素数,上面的方法是一个最最直接的方法,初学者知道这种方法就可以了。
但其实还有很多比这种方法时间复杂度更低的方法,如果想更进一步探索程序的简洁和美妙,我明天会整理发出来给大家参考一下。
这里分享几个很有意思的猜想:
哥德巴赫猜想
哥德巴赫猜想(Goldbach Conjecture)大致可以分为两个猜想(前者称“强”或“二重哥德巴赫猜想”后者称“弱”或“三重哥德巴赫猜想”):1、每个不小于6的偶数都可以表示为两个奇素数之和;2、每个不小于9的奇数都可以表示为三个奇质数之和。
黎曼猜想
黎曼猜想是一个困扰数学界多年的难题,最早由德国数学家波恩哈德·黎曼提出,迄今为止仍未有人给出一个令人完全信服的合理证明。即如何证明“关于质数的方程的所有意义的解都在一条直线上”。
此条质数之规律内的质数月经过整形,“关于质数的方程的所有意义的解都在一条直线上”化为球体质数分布。
孪生质数猜想
1849年,波林那克提出孪生质数猜想(the conjecture of twin primes),即猜测存在无穷多对孪生质数。
猜想中的“孪生质数”是指一对质数,它们之间相差2。例如3和5,5和7,11和13,10016957和10016959等等都是孪生质数。
10016957和10016959是发生在第333899位序号质数月的中旬[18±1]的孪生质数。
质数月定位孪生质数发生位置:
首个质数月孪生质数发生位置:[T-1]*30 【[4±1] [6±1] [12±1] [18±1] [30±1] 】 T=1
其余质数月孪生质数发生位置:[T-1]*30 【[0±1] [12±1] [18±1] [30±1] 】 T=N是自然数代表质数月
相关内容
-
word怎么打钩到方框里|在word中设置可以打钩的
word怎么打钩到方框里|在word中设置可以打钩的方框的方法,方...
-
word文档怎么调行间距|6个Word表格行距调整方法
word文档怎么调行间距|6个Word表格行距调整方法,行间距,方法,...
-
excel怎么合并两个工作表|Excel将两个表格数据
excel怎么合并两个工作表|Excel将两个表格数据合并为一个方...
-
word文档空白页删不掉|word空白页删除不了的解
word文档空白页删不掉|word空白页删除不了的解决方法,删除,文...
-
二进制小数转十进制|计算器怎么算进制步骤
二进制小数转十进制|计算器怎么算进制步骤,算进,步骤,十进制,...
-
excel对勾快捷键|5种快速输入√与×号的方法
excel对勾快捷键|5种快速输入√与×号的方法,输入,方法,快捷...
-
求平均值的公式|Excel中必须掌握的平均值计算技
求平均值的公式|Excel中必须掌握的平均值计算技巧,计算,条件,...
-
计算机二级c语言软件|二级c语言vc2010操作步骤
计算机二级c语言软件|二级c语言vc2010操作步骤,语言,二级,双...
-
excel计算时间差|excel自动记录数据修改时间
excel计算时间差|excel自动记录数据修改时间,修改时间,数据,...
-
pdf修改编辑文字|PDF文档上修改文字的方法
pdf修改编辑文字|PDF文档上修改文字的方法,修改,文字,文档,方...
-
微信安装下载到手机|手机安装微信最简单的方法
微信安装下载到手机|手机安装微信最简单的方法,安装微信,方法...
-
c语言return|c语言中return的作用简单举例
c语言return|c语言中return的作用简单举例,语言,作用,调用函...
-
js数组删除|JavaScript删除数组元素的7种方法
js数组删除|JavaScript删除数组元素的7种方法,删除,数组元素,...
-
cad面域命令怎么用|cad面域正确使用方法
cad面域命令怎么用|cad面域正确使用方法,使用方法,命令,图形,...
-
pdf空白页怎么删除|pdf删除空白页最简单方法
pdf空白页怎么删除|pdf删除空白页最简单方法,方法,删除空白页...