素数算法(2是不是素数)

寻找素数的三种算法,一个比一个快

强烈建议换黑色背景阅读，因为亮光会招虫子，黑色背景体验好眼睛不累，体验好节能环保，体验好NO BUG程序没有BUG

▽关键技能点▽

math loop algorithm

寻找素数的算法相信大家都不陌生。作为基础常用的算法之一，效率是考虑的重点。避免无谓的计算是关键，但怎么判断不必要的计算？先看一个简单栗子：

#找出1千万以内所有能整除n的整数

分别计算三者算法的耗时

start= time.time()

**function**#逐皮洞一调用三种算法

end= time.time()

整除3的耗时结果：

for_loop time: 0.6796061992645264

列表推导式 time: 0.5297579765319824

slice time: 0.20990514755249023

第三种切片的效率最好，1千万以内枚举所有整除3的大致0.2秒！

耗时表现其次是列表推导式。

for循环+条件判断的耗时是切片的三倍之多！

线下课堂上将详细讲为什么会有差别？

问题难度升级：大范围内找所有素数

判断一个数是素数与否，不必从2开始逐一取余直到n-1为止，有童鞋提出只需到n//2为止即可。

其实，还可以‘犯懒’!，取余直到n的开平方取整即可。

为什么可以犯懒，只取到不到n的一半就够判断了呢？

详细见：[算法ABC-4：素数的优化算法]( http://mp.weixin.qq.com/s?

下面算法思路2是不燃羡枯是已经最快的算法了？

不是，今天将介绍比较少见的第三种写法！

今天将在算法ABC-4的基础上，探讨相关的问题，在1千万以内寻找所有****非****质数算法效率如何提高？先找出局部优化的两个小动作：

算法思路-1

遍历1-10000000中每一个数，isPrime(x)判断如果是素数，跳过；不是素数派判添加到ans列表

** Solution 1st**

**算法思路-2****判断一个数不是素数，只要出现第一个能整除的结果立即返回True**这样就不需要一直取余判断直到 n 0.5+1******solution 2nd****

中阶班的逻辑训练必不可少。*注意两种写法all()和any()的区别！

最后，第三种算法不太好理解，详细将在线下分解

算法思路-3

****solution 3rd****

比较以下三种找素数的效率，n=100000

即找出十万以内所有的非素数需要的时间

****solution 3rd****

结论可见，第三种方法效率是第二种的50多倍，十万以内耗时只需0.02秒，而第二种方法耗时要1秒多！

第三种写法详细讲解将在课堂讨论。

求素数最快的算法

如果只是求一首碧搜个数是否是素数的话，那就直接用了循环判断是否能整者历除。反过来如果求小于某一个数之内所有的素数的话，那是用筛法来求最为快捷。效率慧昌最高。

c语言求素数的算法

根据素数的性质，代码设计如下：

设计一：判断n是否能被1~n-1整除，不能整除为素数

#include<stdio.h>

int main()

{

int i, n;

scanf("%d",&n);

for(i= 2; i< n; i++)

{

if(n%i== 0)

break;

}

if(i< n) printf("This is not a prime.");

else printf("This is a prime.");

return 0;

}

设计二：判断n是否能被2~√n间的整数整除，不能整除为素数

#include<stdio.h>

#include<math.h>

int main()

{

int n,i;

double k;

scanf("%d",&n);

k= sqrt(n);

for(i= 2; i<= k;i++)

{

if(n%i== 0) break;

}

if(i<=k) printf("This is not a prime.");

else printf("This is a prime");

return 0;

}

扩展资料：

1.素数的定义是只能被1和他本身整除,1不是素数.因此要皮液判断一个数是否为素数.就要判断梁握激它能不能被比他小的所有素数整除,这是一个算法.(写到算法时,我只能写出用它除橡袜以比他小的所有数,造成运算速度低下)

2.如果一个质数大于根号n，而n可以除尽它，那么n必然也可以除尽一个更小的质数。由此可以得到一个法2较快的素数判断算法

参考资料：百度百科-scanf

参考资料：百度百科-质数

什么是素数算法

素数即只能被1和其本身整除的数，算法判断n是否为素数只需用2~n/2之间的数去除就可以了。因为一个数薯答的一半的平方大于其本身是从数顷慧5开始的，解方程：n/2的平方>n。即一个数n的两个因数不能同时比n/2大。就可以说一个数若不是素数则一定在2~n/2之间有因数。而且2，3也是符合下面程序的。

素数（又称质数）：就是除了1和它本身，没有其他因子的整数。注：1不是素数。

C语言代乎码码算法：

#include<stdio.h>

main(){

int i,j,k=0;

for(i=2;i<=1000;i++)

{

for(j=2;j<=i/2;j++)

if(i%j==0)break;

if(j>i/2)

{printf("%d",i);}

}

}

好了，本文到此结束，如果可以帮助到大家，还望关注本站哦！