线性筛素数(探索中的不断优化)
工欲善其事必先利其器 首先素数是什么？ 素数就是一个数除了1和他本身没有其他因数的数叫做质数。 合数即为对立概念 当然，1既不是素数也不是合数 素因子是什么？ 由欧拉函数得到结论： 每一个合数都可以写成几个素数相乘的形式， 这些素数即为该合数的质因子
我们的目的是建立一张素数表 范围可达1~1e8左右 以bool数组存放，是素数为true 否则为false 基于这些数学定义，有以下算法 素数的高效判断方法 v1.0 全遍历 时间复杂度为O(N)
bool is_prime_1(int n)
{
for (int i = 2; i < n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}v2.0根号优化 时间复杂度为O(sqrt(N)) 不难发现每一对素数的出现总是一个小于sqrt(n),另一个大于sqrt(n). 笔者注：cmath里的sqrt函数实现时间可能比乘法慢上一筹
bool is_prime_2(int n) {
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) {
return false;
}
}
return true;
}v2.5位运算优化 时间复杂度为O(sqrt(N)/2)
思路超级简单易懂
n%2=0数必不为素数
以二进制存放的数最后1bit一定是0,n&1=0
或者直接n%2==0特判
bool is_prime_2.5(int n) {
if (n == 2)
return true;
if ((n & 1) == 0)
return false;
for (int i = 3; i * i <= n; i += 2) {
if (n % i == 0) {
return false;
}
}
return true;
}v3.0 %6筛 时间复杂度为O(sqrt(N)/3) 这个方法有点genius 证明：令x≥1，将大于等于5的自然数表示如下：······ 6x-1，6x，6x+1，6x+2，6x+3，6x+4，6x+5，6(x+1），6(x+1)+1 ······可以看到，不在6的倍数两侧，即6x两侧的数为6x+2，6x+3，6x+4，由于2(3x+1)，3(2x+1)，2(3x+2)，所以它们一定不是素数，再除去6x本身，显然，素数要出现只可能出现在6x的相邻两侧。这里有个题外话，关于孪生素数，有兴趣的道友可以再另行了解一下，由于与我们主题无关，暂且跳过。这里要注意的一点是，在6的倍数相邻两侧并不是一定就是质数。此时判断质数可以6个为单元快进，即将方法（2）循环中i++步长加大为6，加快判断速度，原因是，假如要判定的数为n，则n必定是6x-1或6x+1的形式，对于循环中6i-1，6i，6i+1,6i+2，6i+3，6i+4，其中如果n能被6i，6i+2，6i+4整除，则n至少得是一个偶数，但是6x-1或6x+1的形式明显是一个奇数，故不成立；另外，如果n能被6i+3整除，则n至少能被3整除，但是6x能被3整除，故6x-1或6x+1（即n）不可能被3整除，故不成立。综上，循环中只需要考虑6i-1和6i+1的情况，即循环的步长可以定为6
bool Is_prime3.0(int n)
{
if(n==1) return false;
if(n==2||n==3) return true;
if(n%6!=1&&n%6!=5) return false;
for( int i=5;i*i<=n;i+=6)
if(n%i==0||n%(i+2)==0) return false;
return true;
}v4.0埃拉托斯特尼筛法(埃氏筛）O(nloglogn) 接近线性但不是 基本思想：找到一个素数，不断倍增，得到的数一定不是素数，筛去。
#include<bits/stdc++.h>
using namespace std;
#define max 10000000
bool prime[max];
void seek_prime()
{
memset(prime,true,sizeof(prime));
prime[0]=prime[1]=false;
int t=sqrt(max);
for(int i=2;i<= t;i++)
{
if(prime[i])
{
for(int j=i*i;j<max;j+=i)
{
prime[j]=false;
}
}
}
return ;
}
int main()
{
int n,count=0;
cout<<"输入区间上限:"<<endl;
cin>>n;
seek_prime();
for(int j=1;j<=n;j++)
{
if(prime[j])count++;
}
cout<<count<<endl;
return 0;
}这里有一个小优化，j 从 i * i 而不是从 i + i开始，因为 i(2~ i-1)在 2~i-1时都已经被筛去，所以从i * i开始。 上面的小程功能是找出1~n素数个数 v5.0欧拉线性筛 O(n) 埃氏筛的缺点很明显 ：对于一个合数，有可能被筛多次。例如 30 = 215 = 310 = 5*6……那么如何确保每个合数只被筛选一次呢？我们只要用它的最小质因子来筛选即可 先看代码后解释
/*求小于等于n的素数的个数*/
#include<stdio.h>
#include<string.h>
using namespace std;
int main()
{
int n, cnt = 0;
int prime[100001];//存素数
bool vis[100001];
scanf("%d", &n);
memset(vis, false, sizeof(vis));//初始化假设全为素数
memset(prime, 0, sizeof(prime));
for(int i = 2; i <= n; i++)
{
if(!vis[i])//不是目前找到的素数的倍数
prime[cnt++] = i;//找到素数~
for(int j = 0; j<cnt && i*prime[j]<=n; j++)
{
vis[i*prime[j]] = true;//找到的素数的倍数不访问
if(i % prime[j] == 0) break;//关键！！！！
}
}
printf("%d\n", cnt);
return 0;
}其他都还好 难理解步骤：i % prime[j] == 0，这也是该筛法的优越之处 当 i是prime[j]的倍数时 i一定会被之前prime[j]筛过 证： i = kprime[j] (可证明k<prime[j+1])，如果继续运算 j+1，iprime[j+1] = prime[j]kprime[j+1]，这里prime[j]是最小的素因子，当i = kprime[j+1]时会重复筛，所以才跳出循环。 举个例子 ：i = 8 ，j = 1，prime[j] = 2，如果不跳出循环，prime[j+1] = 3，83 = 243 = 2*12，被之前prime[j],i=12筛。因为欧拉筛法的原理便是通过最小素因子来消除。
腾讯云开发者
