六倍原理法筛质数,比埃氏筛快欧拉筛慢的鸡肋筛法

题目描述

给定一个正整数 n，请你求出 1∼n 中质数的个数。

输入格式

共一行，包含整数 n。

输出格式

共一行，包含一个整数，表示 1∼n 中质数的个数。

数据范围

1≤n≤10^6

输入样例

8

输出样例

4

算法1

六倍原理筛法

时间复杂度 菜鸡不会算QWQ,个人参照埃氏筛和六倍原理突发奇想写出来的筛法

参考文献

六倍原理的证明,请参考大佬的博客: https://blog.csdn.net/Q1368089323/article/details/109871337

C++ 代码

#include<iostream>
using namespace std;
const int N=1e7+10;
bool st[N];
int ans=2;
void get_primes(int x)
{
    for(int i=6;i-1<=x;i+=6)
    {
        if(!st[i-1])
        {
            ans++;
            for(int j=2*i-2;j<=x;j+=i-1)
                st[j]=true;
        }
        if(i+1<=x&&!st[i+1])
        {
            ans++;
            for(int j=2*i+2;j<=x;j+=i+1)
                st[j]=true;
        }
    }
}
int main()
{
    int n;
    while(cin>>n)
    {
        ans=2;
        get_primes(n);
        if(n<=2)
            cout<<n-1<<'\n';
        else
            cout<<ans<<'\n';
    }
    return 0;
}