请考虑性能
while True: try: n=int(input().strip()) num=0 def iszhishu(i): num=i//2 result=True if num==0: result= False else: for j in range(1,num+1): if j!=1 and i%j==0: result= False return result if n<=1: print(0) else: for i in range(2,n): #print(i) if iszhishu(i): #print(i) num+=1 print(num) except: break
使用 普通筛选法--埃拉托斯特尼筛法
先简单说一下原理:
基本思想:素数的倍数一定不是素数
实现方法:用一个长度为N+1的数组保存信息(0表示素数,1表示非素数),先假设所有的数都是素数(初始化为0),从第一个素数2开始,把2的倍数都标记为非素数(置为1),一直到大于N;然后进行下一趟,找到2后面的下一个素数3,进行同样的处理,直到最后,数组中依然为0的数即为素数。
如果n*n > 范围最大值就跳出。
import math
def countPrime(N):
n = int(math.sqrt(N) + 1)
arr = [True] * (N+1)
for i in range(2, n):
for j in range(2, N):
if i * j <= N:
arr[i * j] = False
else:
break
return sum(arr) - 2
print(countPrime(int(input())))