while i <= 100:
j = 2
while j <= i / j: #难点1
if i % j == 0:
break #如果提前提出,j的值<= i / j
j = j + 1
if j > i / j: #难点2
print(i, end=' ')
i = i + 1
其实代码每一句都很简单,就不一一注释了,其实难的是思路。主要是两个地方对J变量的判断
A:while循环,一种常见的是j<=sqrt(i),用这个数的开方(根号)来指定搜索上限,这是因为:
一个数若可以进行因数分解,那么分解时得到的两个数一定是一个小于等于sqrt(n),一个大于等于sqrt(n)——所以只要搜索到根号的地方就可以了,提高了速度。
用i/j的方式是sqrt的一种变种,j<=sqrt(i),由于i>j>1,两边平方后不等式仍然成立
j^2<=i 两边除以j就变成了j <= i / j
B:第二处,根据j的数值来判断i是否是素数。当在循环中找到i % j == 0的情况,循环会提前退出,导致j < i / j——说明不是素数;如果循环没有提前退出,说明i是素数,这时j的值>i / j
1、示例代码
import math
def isPreme(smk):
i = 2
for i in range(2, smk):
j = 2
for j in range(2, int(math.sqrt(i)+1)):
if (i % j == 0):
break
else:
print('%s是素数' % i)
isPreme(20)
2、示例结果
2是素数
3是素数
5是素数
7是素数
11是素数
13是素数
17是素数
19是素数