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

素数筛选算法(埃拉托斯特尼筛法)代码模板（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 = 1000000prime = [0] * maxnprimenum = 0flag = [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=' ')