线性筛素数

2023-08-09 22:14:21 来源：博客园

(资料图片仅供参考)

线性筛素数

原理

线性筛素数是一种用于筛选素数的算法。其基本思想是从2开始，将每个素数的倍数标记为合数，然后从下一个未被标记的数开始，重复这个过程，直到遍历完所有小于等于n的数。

算法流程

初始化一个布尔型数组is_prime[0...n],将所有元素设置为true。
从2开始遍历数组，如果当前数是素数(即is_prime[i]为true),则将其所有的倍数(从2倍开始)标记为合数(即is_prime[j]设为false,其中j = i * k + 1,k为非负整数)。
继续遍历下一个未被标记的数，重复步骤2,直到遍历完所有小于等于n的数。
最后，is_prime[i]为true的数就是所求的素数集合。

C++代码实现

#include // 引入头文件，包含了常用的C++库#define reg register // 定义宏，将变量声明为寄存器类型using namespace std; // 使用标准命名空间// 读取输入，返回一个整数inline int read(){    int x=0,f=1;    char ch=getchar(); // 读取一个字符    while(ch<"0"||ch>"9"){ // 如果字符不是数字        if(ch=="-") f=-1; // 如果是负号，设置标志位为负数        ch=getchar(); // 继续读取下一个字符    }    while(ch>="0"&&ch<="9"){ // 如果字符是数字        x=(x<<1)+(x<<3)+(ch^48); // 将数字转换为二进制并存储在x中        ch=getchar(); // 继续读取下一个字符    }    return x*f; // 返回结果，如果有负号则返回负数}// 输出结果，将整数转换为字符串void write(int x){    if(x<0){        putchar("-"); // 如果是负数，输出负号        x=-x; // 取绝对值    }    if(x>9) write(x/10); // 如果数字大于9,递归调用write函数处理十位数    putchar(x%10+"0"); // 将个位数转换为字符并输出    return ;}const int MAXN=100000008; // 定义常量MAXN为100000008int n,q,Prime[MAXN],cnt; // 定义变量n, q, Prime[]和cntbool isPrime[MAXN]; // 定义布尔数组isPrime[]// 查找素数并将其存储在Prime[]中void find(){    memset(isPrime,1,sizeof(isPrime)); // 将isPrime数组的所有元素初始化为1    isPrime[1]=0; // 将1标记为非素数    for(int i=2;i<=n;i++){ // 从2开始遍历到n        if(isPrime[i]) Prime[++cnt]=i; // 如果i是素数，将其存储在Prime[]中        for(int j=1;j<=cnt&&i*Prime[j]<=n;j++){ // 在Prime[]中查找i的倍数            isPrime[i*Prime[j]]=0; // 将找到的倍数标记为非素数            if(!i%Prime[j]) break; // 如果i能被找到的倍数整除，跳出循环        }    }    return ; // 结束函数}int main(){ // 主函数    n=read(),q=read(); // 从输入中读取n和q的值    find(); // 调用find函数查找素数并存储在Prime[]中    for(reg int i=1;i<=q;++i){ // 对于每个查询，从输入中读取一个数字num,并输出对应的素数        int num=read(); // 从输入中读取num的值        write(Prime[num]); // 将num对应的素数转换为字符串并输出        printf("\n"); // 在每个查询后输出换行符    }    return 0; // 结束程序}

例题及题解

题目：给定一个正整数n,编写一个程序找出小于等于n的所有素数。

解答：使用线性筛素数算法，首先创建一个布尔型数组is_prime[0...n],然后从2开始遍历数组，如果当前数是素数，则将其所有的倍数标记为合数。最后，返回is_prime[i]为true的数组成的向量即可。

关键词：