侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【数学】筛质数

GabrielxD
2022-12-02 / 0 评论 / 0 点赞 / 49 阅读 / 1,306 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-12-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

868. 筛质数


给定一个正整数 nn ,请你求出 1n1 \sim n 中质数的个数。

输入格式

共一行,包含整数 nn

输出格式

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

数据范围

1n1061 \le n \le 10^6

输入样例:

8

输出样例:

4

解题

方法一:朴素筛

思路

对于任意一个大于 1 的正整数 nn,那么它的 xxx>1x > 1 )倍就是合数。

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

本质是:每一个合数 nn 都会被 2n12 \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(NlogN)O(N\log{N})

方法二:埃氏筛

思路

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

可以理解为:每一个大于1且不是质数的数(合数),都有一个小于它本身的质因子。

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

本质是:每一个合数 nn 都会被 2n12 \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(NloglogN)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 的最小质因子,此时就应该退出循环,避免之后重复进行筛选。

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

代码

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)O(N)

0

评论区