题目描述

求 1, 2, … , N 中素数的个数。

输入格式

一行一个整数 N。

输出格式

一行一个整数，表示素数的个数。

样例 #1

样例输入 #1

10

样例输出 #1

4

提示

对于 40% 的数据，1 ≤ N ≤ 10^6。
对于 80% 的数据，1 ≤ N ≤ 10^7。
对于 100% 的数据，1 ≤ N ≤ 10^8。

题解

埃氏筛

时间复杂度 O(n * log log n)，空间复杂度 O(n)

利用以下性质：

• 如果 x 是素数，那么大于 x 的 x 的倍数 2x, 3x, … 一定不是素数

定义数组 flag 用来标记对应的整数是否为素数。从小到大遍历每个数，如果这个数是质数，则将其所有的倍数都标记为合数（除了质数本身）。

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#define PRIME 0
#define NOT_PRIME 1

int main() {
  int n, i, j, count;
  scanf("%d", &n);
  _Bool *flag = (_Bool *)calloc(n, sizeof(_Bool));

  for (i = 2; i <= sqrt(n); i++) {
    if (flag[i - 1] == PRIME)
      for (j = i * i; j <= n; j += i)
        flag[j - 1] |= NOT_PRIME;
  }

  count = n - 1;
  for (i = 2; i <= n; i++)
    count -= flag[i - 1];

  printf("%d", count);
  free(flag);
  return 0;
}