判断质数

· · 个人记录

判断质数

首先，说一个前置知识: 质数。 （相信所有人都知道（？））

质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。

  1. 普通方法

    根据素数的性质，我们只要把这个数 x 从 2 ~ x - 1 遍历即可，如果遍历到的数字 i 是 x 的因数，说明 x 不是质数。我们可以加个优化：由于它能够相乘的数一定是一对一对的，所以我们只要遍历到 sqrt(x) 即可。

code:

#include <bits/stdc++.h>
using namespace std;

int n;

bool isprime(int x) { // 0 = 合数, 1 = 质数 
    if (x <= 1)  // 1 不是质数, 要特判
        return 0;
    if (x == 2)  // 2 是唯一能被 2 整除的质数, 要特判
        return 1;
    for (int i = 2; i * i <= x; i++) {
        // 从 2 ~ sqrt(x), 因为他是一个对, 最大只会到sqrt(x)
        if (x % i == 0)  // 是个合数 
            return 0;
    }
    return 1;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        if (isprime(i))
            printf("%d ", i);
}

  1. 埃氏筛

    埃氏筛，就是用从 2 ~ x - 1遍历，遍历到一个数字 i ，判断一下 i 是否为质数，如果是的话，那么一切 i 的的倍数全都是合数。（竟然有人问我：那 i 的因数呢！）

    code:


 // 2023/3/6
// 2.埃氏筛
// by Kimble (luogu @SKB_Konnyaku)
// 也可在luogu blog查看:https://www.luogu.com.cn/blog/kimble-blog/pan-duan-zhi-shu
#include <bits/stdc++.h>
using namespace std;

int n; // 范围 
bool isprime[1010]; //质数库(存当前找到的所有的质数)[1 = 合, 0 = 质]

void Aiprime(int n) {
    isprime[1] = 1; // 1 不是质数, 标记为合数
    for (int i = 2; i <= n; i++) { // i 从 2 !!!!
        if (isprime[i] == 0) {  // 如果他是质数, 那么就把他所有的倍数标记为合数 
            for (int j = 2 * i; j <= n; j += i)
                // 注意, 是 += i, 不是 * 2, 否则他就是i * 2, i * 4...... 
                isprime[j] = 1;  // 标记为合数 
        }
    }
}
int main() {
    scanf("%d", &n);
    memset(isprime, true, sizeof(isprime)); // 虽然全局默认为0, 但这样更稳妥 
    Aiprime(n);  // 调用合数 
    for (int i = 1; i <= n; i++)
        if (isprime[i] == 0) printf("%d ", i);
    return 0;
}
// bye~

  1. 线性筛

    （一个xxs写的xxs） 对于线性筛，思路与埃氏筛类似，但是在埃氏筛的基础上做了优化：埃氏筛有可能把原来已经设为 false 的再设一遍，所以埃氏筛的时间复杂度并不完美。我们在线性筛里, 做一个这样的判断: 如果 prime[j] 能把 i 整除, 说明再往后的(prime[j + 1], prime[j + 2]......)都能被整除,保证了一个合数只能被筛一次。

code：

// 2023/3/6
// 3.线性筛 (一个xxs写的xxs)
// by Kimble (luogu @SKB_Konnyaku)
// 也可在blog查看:https://www.luogu.com.cn/blog/kimble-blog/pan-duan-zhi-shu
#include <bits/stdc++.h> // 万能头yyds 
using namespace std;

int n; // 范围
int cnt = 0;//当前质数库有多少个元素
bool ok[10010];//标记是否为质数, 1 = 合, 0 = 质
int prime[10010]; //质数库(存当前找到的所有的质数)

int main() {
    scanf("%d", &n);
    memset(ok, true, sizeof(ok)); // 虽然全局默认为0, 但这样更稳妥 
    ok[1] = 1; //1不是质数, 需要特判
    for (int i = 2; i <= n; i++) { // 重要的说三遍: i初始是2! i初始是2! i初始是2!
        if (ok[i] == 0) // 他被标记为质数的话......
            prime[++cnt] = i; //质数库增加
        for (int j = 1; j <= cnt && i * prime[j] <= n; j++) {
            // i * prime[j] 如果已经大于n, 那对我们没有用的, 所以完全不考虑这一部分
            ok[i * prime[j]] = 1; // 他的倍数标记为合数
            if (i % prime[j] == 0)
                break;
            // 如果 prime[j] 能把 i 整除, 说明再往后的(prime[j + 1], j + 2......)都能被整除
            //保证了一个合数只能被筛一次
        }
        // 19~26 将i的质数往后的倍数都标记为合数
    }
    for (int i = 1; i <= cnt; i++)
        printf("%d ", prime[i]);
    return 0;
}
//bye~