摘要
Title: 868. 筛质数
Tag: 埃及筛、线性筛
Memory Limit: 64 MB
Time Limit: 1000 ms

Powered by:NEFU AB-IN

Link

• 题意
• 思路
• 代码

868. 筛质数

• 题意

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

• 思路

  定理：1 ~ n 中有$\frac{n}{ln_n}$个质数

• 代码

  • 埃式筛 $O(nloglogn)$

  N = int(1e6 + 10)
  prime, st, ans = [0] * N, [0] * N, [0] * N
  
  
  def init():
      cnt = 0
      for i in range(2, N):
          if st[i] == 0:
              prime[cnt] = i
              cnt += 1
              for j in range(i + i, N, i):
                  st[j] = 1
          ans[i] = cnt
  init()
  n = int(input())
  print(ans[n])

  • 线性筛 n只会被它的最小质因子筛掉 $O(n)$

  N = int(1e6 + 10)
  st, prime = [0] * N, [0] * N #st代表是否被筛
  cnt = 0
  def init(n):
      global cnt
      for i in range(2, n + 1):
          if st[i] == 0:
              prime[cnt] = i
              cnt += 1
          j = 0
          while i * prime[j] <= n:
              st[i * prime[j]] = 1
              if i % prime[j] == 0:
                  break
              j += 1
      
  n = int(input())
  init(n)
  print(cnt)