python判断素数

Question

如题所述

Answer 1

i = 2
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的一种变种，jj>1，两边平方后不等式仍然成立
j^2<=i

两边除以j就变成了j
<=
i
/
j
B:第二处，根据j的数值来判断i是否是素数。当在循环中找到i
%
j
==
0的情况，循环会提前退出，导致j
< i
/
j——说明不是素数；如果循环没有提前退出，说明i是素数，这时j的值>
i
/
j