埃式筛法

blablabla

样例

#埃式筛法
n = int(input())
st = [False] * (n + 1)
prime = [0] * (n + 1)
cnt = 0

def get_prmes(x):
    global cnt
    for i in range(2, x + 1):
        if st[i] == False:
          prime[cnt] = i
          cnt += 1
          for j in range(i, x + 1, i):
              st[j] = True
              #print(j)

get_prmes(n)
print(cnt)

算法1

(线性筛法 $O(n^2)$

#线性筛法
n = int(input())
st = [False] * (n + 1)
prime = [0] * (n + 1)
cnt = 0

def get_prmes(x):
    global cnt
    for i in range(2, x + 1):
        if st[i] == False:
          prime[cnt] = i
          cnt += 1
        j = 0
        while prime[j] <= n / i: #从小到大枚举质数
            st[prime[j] * i] = True
            if i % prime[j] == 0: #这句话满足是，prime[j]一定是i的最小质因子
                break
            j += 1

get_prmes(n)
print(cnt)

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla