1、新建python文件,testprimenum.py;
2、编写python代码,求1到100之间的素数;
list1 = []
i = 2
for i in range(2,101):
j = 2
for j in range (2,i):
if i%j == 0:
break
else:
list1.append(i)
print(list1)
3、窗口中右击,选择‘在终端中运行Python文件’;
4、查看执行结果,1-100之间的素数为:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
素数的计算方法有很多种。
最朴素的办法是,用所有小于n但大于1的整数去除n,如果均不能除尽,那么,n就是素数。这就是筛法的核心。
进一步,除了2之外,所有素数都是奇数,那么,用于试商的可以只用小于n但大于1的奇素数,并且只对奇数进行试商。
再进一步,如果一个数n可以分解为两个因数相乘,那么,至少其中一个因数是不大于n的平方根的,所以,我们可以对奇数n用不小于n的平方根但大于1的奇素数去试商。
到这一步,已经可以用来对一个比较小的数进行进行“是否是素数”的检查了。麻烦的只是需要建立一个素数表,记录从小到大我们找到的每一个素数。
参考以下代码:
素数计算
筛法还有更高的应用方式,比如while中对i不是每次加而是每次加素数表前若干个数的积,如6,30,210中的某一个。(2是第一个素数)这种需要更多的控制,实现复杂,对速度的提升远没有只对奇数试商和只用平方根以下的素数试商的提升大。
除了筛法以外,还有其它的方式去判断一个数是不是素数,这里就不罗列了。
对于这道练习题,会筛法就足够了,想进一步提升,你可以在上图给出的方法的基础上尝试用步长为6的循环来做,如果做到了,那么步长为30或更大的就只是体力活了。