线性筛法
质数从2开始记录,到这个数本身停止,发现这个数是质数时,将其加入数组,并且计数个数加一,
然后在1~n的范围内,将所有的i*primes[j]状态全部转化为True,说明他们为合数,若i%primes[j]==0 ,则说明i==j或i为合数,使循环停止。
样例
def get_prime(x):
i = 2 # 质数从而开始
cnt = 0 # 记录质数个数
while i<=x: # 记录到x时停止
if not st[i]:
primes[cnt] = i
cnt+=1
j = 0
while primes[j]<=x//i:
st[primes[j]*i] = True
if i % primes[j]==0:
break
j+=1
i+=1
return cnt
n = int(input())
st = [False] * (n+1)
primes = [0] * (n)
print(get_prime(n))