数论-求n以内的质数

一、埃拉托斯特尼筛法

  名字很高大上,然而并没有什么卵用……

思路:

  在把<=√n的质数所有的<=n的倍数剔除,剩下的就都是质数了,很容易理解……

  复杂度O(nloglogn)

 #include<cmath>
const int MAXN=;
int b[MAXN/],top;
bool a[MAXN];
void cal_prime_num(int n)
{
k=sqrt(n);
for(int i=;i<k;i++)
{
if(!a[i])
{
int j=;
b[++top]=i;
while(i*j<n)
{
a[i*j]=true;
++j;
}
}
}
}

二、欧拉筛

  上一个筛法似乎复杂度不大,但是遇到107规模的数据就会炸,主要是因为一个数会被不同的质数筛好几遍,欧拉筛保证一个合数只被它的最小质因子筛去一遍,这就是整个代码最核心的部分,也是难理解的部分,然而只有一句话:

if(!i%pri[j])break;

  证明转自他人博客:

prime数组中的素数是递增的,当 i 能整除 primej,那么 i*primej+1这个合数肯定被primej乘以某个数筛掉。
因为i中含有primej,primej比primej+1小。接下去的素数同理。所以不用筛下去了。
在满足i%prmej==0这个条件之前以及第一次满足改条件时,primej必定是primej*i的最小因子。

  复杂度O(n)

  其余的代码就很容易理解了:

 #include<cmath>
const int MAXN=;
int b[MAXN/],top;
bool ispri[MAXN];
void cal_prime_num(int n)
{
for(int i=;i<=n;++i)
{
if(!ispri[i])pri[++top]=i;
for(int j=;j<=top&&i*pri[j]<=n;++j)
{
ispri[i*pri[j]]=true;
if(!i%pri[j])break;
}
}
}
上一篇:c# 任务超时执行组件


下一篇:第一百零二节,JavaScript函数