埃筛 + 欧拉筛法分析算法原理

埃筛

原理

利用已知的质数来确定这个数的倍数不是质数，从而达到优化算法的目的。

时间复杂度为$O(n* loglogn)$O(n∗loglogn)
能够处理1e6级别的数据。比较优秀。

但是如下图所示，它依旧有劣势，那就是已经筛选过的数可能会被再筛选一遍。

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e5 + 5;
bool isprime[maxn];
void Aishai(int n)
{
  isprime[0] = isprime[1] = false;
  for(int i = 2;i * i <= n;i++)
  {
      if(isprime[i])
      {
          for(int j = i * 2;j <= n;j += i)
          {
              isprime[j] = false;
          }
      }
  }
}
int main()
{
    int n;
    cin >> n;
    memset(isprime, true, sizeof isprime);
    Aishai(n);
    for(int i = 2;i <= n;i++)
    {
        if(isprime[i])
            cout << i << endl;
    }
    return 0;
}

欧拉筛法

作为埃氏筛法的进一步优化，省去的重复的步骤，使时间复杂度降到了
算法分析：
优化依托的思想即让每个数都由它的最小质因子筛选出来。
比如6 就可以被2 筛选出来。那么就不会存在重复的晒去同一个数的情况。
if(i % prime[j] == 0) break; 这是每个数只能被它的最小质因子筛去的核心代码。
为什么?
首先我们明确，prime存储的质数一定是递增的，那么我们假设现在有一个index = m,m > j。那么假设不去执行break,那么就会有i * prime[m]被筛去，我们假设 存在k，满足 k * prime[j] = i; 那么就有k * prime[j] * prime[m]被筛去。令T = k * prime[j] * prime[m],我们会发现此时的这个数是被prime[m]筛去的，而实际上，它的最小质因子应该是prime[j]。
那么再以后的筛法中，这个数又会被重复的筛去，从而增加了操作次数。

$O(n)$O(n)

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn = 1e5 + 5;
int prime[maxn];
bool vis[maxn];
void sieve(int n)
{
    int cnt = 0;
    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; //关键！！！！
        }
    }
}
int main()
{
    memset(vis, false, sizeof vis);
    int n;
    cin >> n;
    sieve(n);
    int cnt = 0;
    for(int i = 2; i <= n; i++)
    {
        if(!vis[i])
        {
            cnt++;
            cout << i << " ";
            if(cnt % 10 == 0)
                cout << endl;

        }
    }
    return 0;
}