素数筛选算法(埃拉托斯特尼筛法)代码模板（C/C++/Java/Python多版本）

素数筛选算法，最经典的埃拉托斯特尼筛法，其基本思想是从2开始，依次将每个素数的倍数标记为合数，最终未被标记的数即为素数。它高效直观，时间复杂度约为O(n log log n)，适合一次性筛选较大范围内的所有素数。

1. C/C++版代码：

// 位操作求素数（位筛法）
const int maxn = 1000000;
int prime[maxn], primenum;
int flag[maxn / 32 + 1];  // 每个int存储32个数的素性信息
// 生成素数并保存到prime数组
void wei_prime(int t) {
    primenum = 0;
    flag[0] |= 3;  // 标记0和1为非素数
    for (int k = 1; k <= t / 32 + 1; k++) flag[k] = 0;
    
    for (int i = 2; i <= t; i++) {
        if (!((flag[i / 32] >> (i % 32)) & 1)) {  // 检查第i位是否为0（素数）
            for (int j = i * i; j <= t; j += i)  // 从i*i开始标记
                flag[j / 32] |= (1 << (j % 32));  // 标记j为非素数
            prime[primenum++] = i;
        }
    }
}
// 仅生成标记数组，不保存素数
void wei_prime_onlyflag(int t) {
    flag[0] |= 3;
    for (int k = 1; k <= t / 32 + 1; k++) flag[k] = 0;
    
    for (int i = 2; i <= t; i++) {
        if (!((flag[i / 32] >> (i % 32)) & 1)) {
            for (int j = i * 2; j <= t; j += i)  // 从i*2开始标记
                flag[j / 32] |= (1 << (j % 32));
        }
    }
}
// 根据标记数组输出所有素数
void printby_flag(int t) {
    for (int i = 0; i <= t; i++) {
        if (!((flag[i / 32] >> (i % 32)) & 1))
            printf("%d ", i);
    }
}

2. Java版代码：

public class WeiPrime {
    static final int maxn = 1000000;
    static int[] prime = new int[maxn];
    static int primenum;
    static int[] flag = new int[maxn / 32 + 1];  // 每个int存储32个数的素性信息
    
    // 生成素数并保存到prime数组
    static void wei_prime(int t) {
        primenum = 0;
        flag[0] |= 3;  // 标记0和1为非素数
        for (int k = 1; k <= t / 32 + 1; k++) flag[k] = 0;
        
        for (int i = 2; i <= t; i++) {
            if (((flag[i / 32] >> (i % 32)) & 1) == 0) {  // 检查第i位是否为0
                for (int j = i * i; j <= t; j += i)  // 从i*i开始标记
                    flag[j / 32] |= (1 << (j % 32));  // 标记j为非素数
                prime[primenum++] = i;
            }
        }
    }
    
    // 仅生成标记数组，不保存素数
    static void wei_prime_onlyflag(int t) {
        flag[0] |= 3;
        for (int k = 1; k <= t / 32 + 1; k++) flag[k] = 0;
        
        for (int i = 2; i <= t; i++) {
            if (((flag[i / 32] >> (i % 32)) & 1) == 0) {
                for (int j = i * 2; j <= t; j += i)  // 从i*2开始标记
                    flag[j / 32] |= (1 << (j % 32));
            }
        }
    }
    
    // 根据标记数组输出所有素数
    static void printby_flag(int t) {
        for (int i = 0; i <= t; i++) {
            if (((flag[i / 32] >> (i % 32)) & 1) == 0)
                System.out.print(i + " ");
        }
    }
}

3. Python版代码：

maxn = 1000000
prime = [0] * maxn
primenum = 0
flag = [0] * (maxn // 32 + 1)  # 每个元素存储32个数的素性信息
# 生成素数并保存到prime数组
def wei_prime(t):
    global primenum
    primenum = 0
    flag[0] |= 3  # 标记0和1为非素数
    for k in range(1, t // 32 + 2):
        flag[k] = 0
    
    for i in range(2, t + 1):
        if ((flag[i // 32] >> (i % 32)) & 1) == 0:  # 检查第i位是否为0
            j = i * i
            while j <= t:  # 从i*i开始标记
                flag[j // 32] |= (1 << (j % 32))  # 标记j为非素数
                j += i
            prime[primenum] = i
            primenum += 1
# 仅生成标记数组，不保存素数
def wei_prime_onlyflag(t):
    flag[0] |= 3
    for k in range(1, t // 32 + 2):
        flag[k] = 0
    
    for i in range(2, t + 1):
        if ((flag[i // 32] >> (i % 32)) & 1) == 0:
            j = i * 2
            while j <= t:  # 从i*2开始标记
                flag[j // 32] |= (1 << (j % 32))
                j += i
# 根据标记数组输出所有素数
def printby_flag(t):
    for i in range(t + 1):
        if ((flag[i // 32] >> (i % 32)) & 1) == 0:
            print(i, end=' ')