题目描述

blablabla

样例

#include <iostream>
#include <algorithm>

using namespace std;

const int N= 1000010;

int primes[N], cnt;//存储质数的数组，cnt是质数个数 
bool st[N]; 

void get_primes_1(int n)
{

    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;//i是质数 
        for (int j = 0; primes[j] <= n / i; j ++ )//枚举最小质数 
        {

            st[primes[j] * i] = true;
            //primes数组里一定都是质数 ，将质数的倍数筛掉 
            // 如果 i 是 素数的倍数，则停止后面的标记。
            // 因为后续的，i 倍数的合数，
            // 一定能等待到被 primes[j] 标记 
            if (i % primes[j] == 0) break;
        }
    }
}
void get_primes_2(int n)
{
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) primes[cnt++]=i;//当前这个数i没有被筛过，说明i是质数 
        for(int j=i+i;j<=n;j+=i) st[j]=true;//依次去掉从2到n的所有数的倍数，不管质数还是和数的倍数都筛掉，剩下的一定全都是质数
        //可能筛的时候有重复的。 
    }
}
int main()
{
    int n;
    cin >> n;
    get_primes_1(n);
    cout << cnt << endl;
    for(int i=0;i<cnt;i++) cout<<primes[i]<<" ";

    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla