素数筛多种方法（朴素法，埃氏筛，欧拉筛(线性筛)，区间筛）1e11内的素数总数？

素数筛多种方法（朴素法，埃氏筛，欧拉筛(线性筛)，区间筛）1e11内的素数总数？

本文参照多位大佬关于素数筛的博客进行总结和完善。对于寻找素数，我们第一时间想到的便是二重循环暴力查找，通过循环中只判断到根号n可以优化一些，不过复杂度也达不到预期。数论中有一种时间复杂度O(nloglogn)的埃氏筛算法，而在一些数据范围达到1e7这样的题目中，也很难让人满意，于是便可使用欧拉筛法，也即时间复杂度只有 O(n)的线性筛法。文末附带大佬快速查找1e11范围内素数总数的代码。

文章目录

• • 朴素法(暴力)——时间复杂度 O(n*sqrt(n))
  • 埃式筛(Eratosthenes)——时间复杂度O(nloglogn)
  • 欧拉筛(线性筛)—— 时间复杂度为O(n)
  • 区间筛(求一定区间内的素数总数)
  • 1e11内的素数总数--HDU 5901

朴素法(暴力)——时间复杂度 O(n*sqrt(n))

暴力遍历，也叫试除法。对[2,sqrt(n)]内的数进行遍历判断，最坏情况下，要遍历区间内所有值才可得结果(效率低)
虽然不太实用，但这是判断一个数是否为素数的最基础思路，对后续的多种高效率筛法也有帮助

bool isprime(int n)
{int i;for(i=2;i<=sqrt(n);i++)if(n%i==0)return false;return true;
}

埃式筛(Eratosthenes)——时间复杂度O(nloglogn)

• 前言
  既然一个个找素数非常费时间，我们可以换个思路，先把不是素数的数（合数）给找出来，开一个较大的int型或者bool型数组，把不是素数的数（合数）给标记好，那么剩下的未标记的就全是素数了
  那怎么找不是素数的数（合数）呢？当我们已知一个数n是素数时，那么n的整数倍n*i（i>=2）则必定不是素数
• 思路
  从2开始，将每个质数的倍数都标记成合数，以达到筛选素数的目的

bool number[maxn+5];
void isprime()
{int i,j;memset(number,true,sizeof(number));for(i=2;i<=maxn;i++){if(number[i]==true){for(j=2;j*i<=N;j++)number[i*j]=false;}}
}

• 缺陷
  对于一个合数，有可能被筛多次（多次判断），这样就有大量的数在筛选过程中判断了不止一次。
  例如： 30 = 2 * 15 = 3 * 10 = 5 * 6……
• 改进
  已知n为素数时，从n*n开始并依次累加进行筛选，这样便减少了上面方法中大量的重复筛选

bool number[maxn+5];
void isprime()
{int i,j;memset(number,true,sizeof(number));for(i=2;i<=sqrt(N);i++){if(number[i]==true){for(j=i*i;j<=N;j+=i)number[j]=false;}}
}

• 思考
  换成n*n开始筛选也不能完全避免筛选过程中的重复，那么如何确保每个合数只被筛选一次呢？我们只要用它的最小质因子来筛选即可，这便是欧拉筛法

欧拉筛(线性筛)—— 时间复杂度为O(n)

• 思想
  在埃氏筛法的基础上，让每个合数只被它的最小质因子筛选一次，以达到不重复判断，优化筛选过程的目的

/*求小于等于n的素数的个数*/
#include<stdio.h>
#include<string.h>
using namespace std;
const int maxn=1e6+5;int prime[maxn],cnt;//存素数 
bool vis[maxn];//保证不做素数的倍数 
void getprime(int n)
{cnt=0;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 && 1LL*i*prime[j]<=n; j++){vis[i*prime[j]] = true;//找到的素数的倍数不访问 if(i % prime[j] == 0) break;//关键！！！！ }}
}
int main()
{int n;scanf("%d",&n);getprime(n);printf("%dn",cnt); return 0;
}

• 解释
  首先，任何合数都能表示成多个素数的积。所以，任何的合数肯定有一个最小质因子。我们通过这个最小质因子就可以判断什么时候不用继续筛下去了。
  其中最难理解的一步是 if(i%prime[j]==0) break；
  如果i%prime[j]==0，那么i就可以看成prime[i]乘以一个数(记为m)；因为我们存的prime是从小到大存的，所以prime[j+1]>prime[j]；那么i * prime[j+1]就可以看成prime[j] * m * prime[j+1]；那么i * prime[j+1]的最小质因子是prime[j]。加上if(i%prime[j]==0) break后我们就可以保证每一个数只被它的最小质因子给筛去，即每一个数只会被筛一次。
  举个例子，6=2*3；当i=2时i%2=0，跳出循环，那它就不会被质因子3给筛去；当i=3时，6就被质因子2给筛去。

区间筛(求一定区间内的素数总数)

• 问题：给定整数 a 和 b，请问区间 [a,b) 内有多少个素数？（a<b≤1e12,b−a≤1e6）

因为 b 以内合数的最小质因数一定不会超过 sqrt（b），因为如果存在 d 是 n 的约数，那么 n/d 也是 n 的约数，由 n=d×n/d 可知 min(d,n/d) ≤ sqrt（n）。如果有 sqrt（n） 以内的素数表的话，就可以把埃式筛法用在 [a,b) 上了。也就是说，先分别做好 [2, sqrt（b）)的表和 [a,b) 的表，然后从 [2, sqrt（b）) 的表中筛得素数的同时，也将其倍数从 [a,b) 的表中筛去，最后剩下的就是区间 [a,b) 内的素数了

假如要求 [1e9,1e9+2) 区间内的素数，难道我们要开 1e9+3 大小的数组吗？其实并不用，我们利用下标偏移，可以减少空间开销。即将 [1e9,1e9+2) 对应到[0,2)，整体区间向左偏移 1e9

typedef long long ll;
const int MAXN = 1e5;
bool is_prime[MAXN];
bool is_prime_small[MAXN];
ll prime[MAXN];
ll prime_num = 0;
//对区间[a,b)内的整数执行筛法，is_prime[i-a]=true <=> 表示i是素数（下标偏移了a） 
void segment_sieve(ll a, ll b) {for (ll i = 0; i * i < b; i++) //对[2,sqrt(b))的初始化全为质数is_prime_small[i] = true;for (ll i = 0; i < b - a; i++) //对下标偏移后的[a,b)进行初始化is_prime[i] = true;for (ll i = 2; i * i < b; i++) { //筛选[2,sqrt(b))if (is_prime_small[i]) {for (ll j = 2 * i; j * j < b; j += i) is_prime_small[j] = false;//(a+i-1)/i 得到最接近a的i的倍数，最低是i的2倍，然后筛选for (ll j = max(2LL, (a + i - 1) / i) * i; j < b; j += i)is_prime[j - a] = false;}}for (ll i = 0; i < b - a; i++) //统计个数 if (is_prime[i])prime[prime_num++] = i + a;
}

1e11内的素数总数–HDU 5901

HDU 5901 Count primes
题意：求不大于n的素数的个数。 n范围是1e11…
来自某大佬极为精简的代码（可做素数查找模板），本蒟蒻看不懂

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;long long n, p[340000], v[340000];void solve()
{long long i,j,m;for(m=1; m*m<=n; ++m)p[m] = n/m-1;for(i=1; i<=m; ++i)v[i] = i-1;for(i=2; i<=m; ++i){if(v[i] == v[i-1]) continue;for(j=1; j<=min(m-1,n/i/i); ++j)if(i*j < m) p[j] -= p[i*j]-v[i-1];else p[j] -= v[n/i/j]-v[i-1];for(j=m; j>=i*i; --j)v[j] -= v[j/i]-v[i-1];}
}int main()
{while(scanf("%lld",&n)!=EOF){solve();printf("%lldn",p[1]);}return 0;
}