素数筛法(sieve of primer number)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2023-06-21 12:35:06
 * 最后修改: 2025-03-01 10:41:52
 * 文件描述:  埃氏筛素数  O(nloglogn)
****************************************************************/

#include <iostream>
#include <cmath>
using namespace std;
 
const int maxn = 1000000;
bool isPrimer[maxn];    // i是合数isPrimer[i]为1，i是素数，isPrimer[i]为0
 
void sieve(long long n){
    int m = sqrt(n);
    isPrimer[2] = 0;
/*
从i*i开始筛选，小于i的数在之前的循环已经筛过，比如6是在i=2时候筛过了，所以j=3时就从3*3开始。
另外，由于i筛选的时候可能会重复前面已经筛过的，比如18，就是在i=2和3时，都筛一遍。
*/
    for (long long i = 2; i <= m; i++) {
        if (!isPrimer[i]){
            for (long long j = i * i; j <= n; j += i){
                isPrimer[j] = 1;
            }
        }
    }
}
 
int main(){
    long long n;
    cin >> n;
    sieve(n);
    for (long long i = 2; i < n; i++){
        if (isPrimer[i] == 0) cout << i << ' ';
    }
       
return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2023-06-21 20:39:52
 * 最后修改: 2025-03-01 11:52:29
 * 文件描述: 线性筛素数  O(n)
****************************************************************/
// 线性筛法是从小到大筛选，但是每个数只会被最小质因子筛选一次。

#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 100000001;
vector<bool> visited(MAXN, false); // 标识数组，visited[i] = true 说明 i 是合数
vector<int> prime; // 存储质数的数组

int main() {
    int n;
    cin >> n;

    for (int i = 2; i <= n; i++) {
        if (!visited[i]) {
            prime.push_back(i); // 如果 i 是质数，添加到 prime 数组中
        }
        // 从最小的质数开始枚举
        for (int j = 0; j < prime.size() && prime[j] * i <= n; j++) {
            int k = prime[j];
            visited[i * k] = true; // 标记合数
            // 如果 i 是质数，当 k = i 时，退出
            // 如果 i 是合数，当 k 等于 i 的最小质因子时退出
            if (i % k == 0) break;
        }
    }

    cout << prime.size(); // 输出质数的个数
    return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2025-07-28 13:32:30
 * 最后修改: 2025-07-28 13:41:04
 * 文件描述: 输出所有小于 MAXN 的“超级素数”：
 *          一个数是超级素数，当它本身是素数，且它的所有相邻子数也都是素数。
****************************************************************/
#include <bits/stdc++.h>
using namespace std;

// 判断一个整数是否为素数
bool Prime_Number_Judge(const int &num) {
    if (num <= 3)
        return num > 1; // 2 和 3 是素数，1 不是
    for (int i = 2; i * i <= num; i++)  // 从 2 遍历到 sqrt(num)
        if (num % i == 0)
            return false; // 找到因数就不是素数
    return true;
}

// 获取一个整数的位数
int Get_Number_Size(const int &num) {
    int digit = 0, val = num;
    while (val) {
        val /= 10;
        digit++;  // 每除一次10就多一位
    }
    return digit;
}

// 将一个整数拆成数字（高位到低位），存入 digits 向量
vector<int>& Get_Digits(const int &num, vector<int> &digits) {
    int num_size = Get_Number_Size(num);
    for (int i = num_size; i > 0; i--) {
        // 取第 i 位的值
        int vactor_val = num % (int)pow(10.0, i);
        vactor_val = vactor_val / (int)pow(10.0, i - 1);
        digits.push_back(vactor_val);
    }
    return digits;
}

// 获取一个整数所有相邻子数（长度从 1 到 n），存入 adjacent 向量
vector<int>& Get_K_Adjacent(const int &num, vector<int> &adjacent) {
    vector<int> digits_number;
    Get_Digits(num, digits_number);  // 先拆位
    int digits = digits_number.size();

    // i 表示子数的长度 - 1（从 0 开始，所以等于实际长度减一）
    for (int i = 0; i < digits; i++) {
        // j 表示起始位置（确保不会越界）
        for (int j = 0; j < digits - i; j++) {
            string buf;
            for (int k = 0; k <= i; k++) {
                // 拼接连续的数字字符
                buf += to_string(digits_number.at(j + k));
            }
            // 将拼接后的字符串转为整数并加入结果中
            adjacent.push_back(stoi(buf));
        }
    }
    return adjacent;
}

int main() {
    int MAXN = 100; // 设置上限，小于该值的数将被检查
    int count = 0;  // 超级素数计数器

    // 枚举所有小于 MAXN 的数
    for (int i = 1; i < MAXN; i++) {
        if (Prime_Number_Judge(i)) { // 如果 i 是素数
            vector<int> buf;
            Get_K_Adjacent(i, buf);  // 获取所有相邻子数
            bool allPrime = true;
            for (int j = 0; j < buf.size(); j++) {
                if (!Prime_Number_Judge(buf.at(j))) {
                    allPrime = false; // 只要有一个子数不是素数，就退出
                    break;
                }
            }
            if (allPrime) {
                cout << i << ' ';  // 输出符合要求的超级素数
                count++;           // 计数加一
            }
        }
    }

    cout << '\n';
    cout << "total count: " << count << endl; // 输出总个数
    return 0;
}