【数学】筛质数

题目

868. 筛质数

---

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

输入格式

共一行，包含整数 $n$ 。

输出格式

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

数据范围

$1 \le n \le 10^6$

输入样例：

8

输出样例：

4

解题

方法一：朴素筛

思路

对于任意一个大于 1 的正整数 $n$，那么它的 $x$ （ $x > 1$ ）倍就是合数。

从小到大枚举 $2 \dots n$，枚举到 $i$ 时 ，把 $i$ 的 $2 \dots \lfloor\frac{n}{i}\rfloor$ 倍数标记为合数，如果枚举到该数时，该数还未被标记为合数（说明 $2 \dots i-1$ 中没有 $i$ 的因数，符合质数的定义），那么他就是一个质数，计数(cnt)增加。

本质是：每一个合数 $n$ 都会被 $2 \dots n-1$ 中的数筛掉。

代码

import java.util.*;
import java.io.*;

public class Main {
    static int countPrimes(int n) {
        int cnt = 0;
        int[] primes = new int[n + 1];
        boolean[] isNotPrime = new boolean[n + 1];
        for (int i = 2; i <= n; ++i) {
            if (!isNotPrime[i]) primes[cnt++] = i;
            for (int j = i + i; j <= n; j += i) isNotPrime[j] = true;
        }
        return cnt;
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        System.out.println(countPrimes(n));
    }
}

#include <iostream>

using namespace std;

const int N = 1e6 + 10;
int primes[N];
bool is_not_prime[N];

int count_primes(const int n) {
    int cnt = 0;
    for (int i = 2; i <= n; ++i) {
        if (!is_not_prime[i]) primes[cnt++] = i;
        for (int j = i + i; j <= n; j += i) is_not_prime[j] = true;
    }
    return cnt;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", count_primes(n));
    
    return 0;
}

时间复杂度：$O(N\log{N})$ 。

方法二：埃氏筛

思路

根据算术基本定理：每个大于1的自然数，要么本身就是质数，要么可以写为2个或以上的质数的积，而且这些质因子按大小排列之后，写法仅有一种方式。

可以理解为：每一个大于1且不是质数的数（合数），都有一个小于它本身的质因子。

也就是说，我们在筛质数的时候只用质数来筛就能达到目的。

本质是：每一个合数 $n$ 都会被 $2 \dots n-1$ 中的质数筛掉。

代码

import java.util.*;
import java.io.*;

public class Main {
    static int countPrimes(int n) {
        int cnt = 0;
        int[] primes = new int[n + 1];
        boolean[] isNotPrime = new boolean[n + 1];
        for (int i = 2; i <= n; ++i) {
            if (!isNotPrime[i]) {
                primes[cnt++] = i;
                for (int j = i + i; j <= n; j += i) isNotPrime[j] = true;
            }
        }
        return cnt;
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        System.out.println(countPrimes(n));
    }
}

#include <iostream>

using namespace std;

const int N = 1e6 + 10;
int primes[N];
bool is_not_prime[N];

int count_primes(const int n) {
    int cnt = 0;
    for (int i = 2; i <= n; ++i) {
        if (!is_not_prime[i]) {
            primes[cnt++] = i;
            for (int j = i + i; j <= n; j += i) is_not_prime[j] = true;
        }
    }
    return cnt;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", count_primes(n));
    
    return 0;
}

时间复杂度：$O(N\log\log{N})$ 。

方法三：线性筛（欧拉筛）

思路

因为 primes 中质数是递增的，所以：

• 如果 primes[j] % i != 0 ：说明 i 的最小质因数还没有找到，即 i 的最小质因数一定大于 primes[j]。也就是说 primes[j] 就是 primes[j] * i 的最小质因数，于是 primes[j] * i 被它的最小质因数筛掉了。
• 如果 primes[j] % i == 0 ：说明 i 的最小质因数是 primes[j]，因此 primes[j] * i 的最小质因子也是prime[j] ，但之后接着用 isNotPrime[primes[j+1] * i]=true 去筛合数时，就不是用最小质因子去更新了，因为 i 有最小质因子 primes[j] $<$ primes[j+1] ，此时的 primes[j+1] 不是 primes[j+1] * i 的最小质因子，此时就应该退出循环，避免之后重复进行筛选。

本质是：每一个合数 $n$ 都会被它的最小质因子筛掉。

代码

import java.util.*;
import java.io.*;

public class Main {
    static int countPrimes(int n) {
        int cnt = 0;
        int[] primes = new int[n + 1];
        boolean[] isNotPrime = new boolean[n + 1];
        for (int i = 2; i <= n; ++i) {
            if (!isNotPrime[i]) primes[cnt++] = i;
            for (int j = 0; primes[j] <= n / i; ++j) {
                isNotPrime[primes[j] * i] = true;
                if (primes[j] % i == 0) break;
            }
        }
        return cnt;
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int) in.nval;
        System.out.println(countPrimes(n));
    }
}

#include <iostream>

using namespace std;

const int N = 1e6 + 10;
int primes[N];
bool is_not_prime[N];

int count_primes(const int n) {
    int cnt = 0;
    for (int i = 2; i <= n; ++i) {
        if (!is_not_prime[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; ++j) {
            is_not_prime[primes[j] * i] = true;
            if (primes[j] % i == 0) break;
        }
    }
    return cnt;
}

int main() {
    int n;
    scanf("%d", &n);
    printf("%d\n", count_primes(n));
    
    return 0;
}

时间复杂度：$O(N)$ 。