算法题 筛质数（Python）

题目：

给定一个正整数n，请你求出1~n中质数的个数。

输入格式

共一行，包含整数n。

输出格式

共一行，包含一个整数，表示1~n中质数的个数。

数据范围

1≤n≤10^6

输入样例：

8

输出样例：

4

代码：

方法1：诶氏筛法 O(nloglogn)

n = int(input())
st = [True]*(n+1)
cnt = 0
primes = []
for i in range(2, n+1):if st[i]: cnt += 1primes.append(i)for j in range(2*i, n+1, i): st[j] = False 
print(cnt)

方法2：线性筛法 O(n)

n = int(input())
st = [True]*(n+1)
cnt = 0
primes = []
for i in range(2, n+1):if st[i]: cnt += 1primes.append(i)for p in primes:if p > n//i: breakst[p*i] = Falseif i % p == 0: break # i是p的倍数，就不用再继续了
print(cnt)

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！