用于需要求某个数是不是素数

素数的定义：当一个整数仅能被1整除时，这个数为素数

筛法的原理：利用定义算法——如果可以被除1及素数本身的其他数整除，则这个数不是素数。那么就去除要求范围内所有合数、0和1，剩下的就是素数了！

（遍历原则：合数都是素数的倍数）

普通的线性筛法：

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

#define ll long long 
const int Max = 100000;  //最大范围[2,Max)
ll su[Max], cnt;
bool isprime[Max]; //isprime[i]的0默认为素数，1为非素数
void prime(){
    cnt = 1;
    //memset(isprime,1,sizeof isprime); //初始化列表的函数，此处为错误使用，因只能赋值为0，-1
    isprime[0]=isprime[1]= 1; // 0和1不是素数
    for(ll i=2 ;i < Max;i++){ //注意非=，防数组溢出
        if(!isprime[i]){ //是素数则保存
            su[cnt++]= i;
            for(ll j = i*2; j<=Max ; j += i){// 素数的倍数都为合数
            isprime[j]=1;
            }
        }

    }
}

int main()
{
    prime();
    for(ll i=1;i<cnt;i++){
        cout<<su[i];
    }
    return 0;
}

虽然这极大的减小了判断时间，但依然有些重复计算。比如判断2的时候，2*3；判断3的时候，3*2 重复筛了一遍6

你们一定想到了，上面的说是普通，那么一定还有优化版

筛选小于等于素数i与i的乘积，便可尽量减少重复的筛选，也不会有遗落

优化后的线性筛法：

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

#define ll long long 
const int Max = 10000; //最大范围[2,Max)
ll su[Max],cnt;
bool isprime[Max];
void prime(){
    cnt =1 ;
    isprime[0]=isprime[1]=1;
    for(ll i=2; i <Max ; i++){//注意非=，防数组溢出

        if(!isprime[i]){
            su[cnt++]=i;
            }
        for(ll j=1; j<cnt && su[j]*i<Max ; j++){ //遍历当前su数组
                isprime[su[j]*i]=1;     //标记为非素数
        }
    }
}

int main()
{
    prime();
    for(ll i=1;i< cnt; i++){
        cout<<su[i]<<endl;
    }
    return 0;
}
防止数组溢出



全文完

—

你以为这就结束了？

还能更好（调整次序，使其只被删除一次）

https://blog.csdn.net/qq_41785863/article/details/80632207《C语言名题精选百则（技巧篇）》，冼镜光 编著，机械工业出版社，2005年7月第一版列举

放在后面

据说第二种方法用时是第一种的八分之一，自己动手丰衣足食，试试看把

//测试程序速度
#include<iostream>
#include<ctime>
using namespace std;
int main()
{
    clock_t start,finish;
    start=clock();  
        //输入你要测试的程序
    finish=clock();
    cout << finish-start   << "/" << CLOCKS_PER_SEC  << " (s) "<< endl;
    return 0;
}
//什么？速度显示为0？ 你为什么不扩大数据规模呢！？ 就像测一页纸的厚度

only love & learning