q浅安时光p

用户名：1620533524

访问量：576

签　名：

等　　级
排　　名	9826
经　　验	1128
参赛次数	0
文章发表	2
年　　龄	0
在职情况	学生
学　　校	兰州大学
专　　业

　　自我简介：

TA的其他文章

[递归]母牛的故事-题解（C++代码）类似斐波那契数列
浏览：166

用筛法求之N内的素数。 -题解（C++代码）
浏览：153

你可能喜欢

用筛法求之N内的素数。 -题解（C++代码）

　　作者: q浅安时光p　　　　发表时间：2021-02-01 11:58:12 浏览：153　|　评论：0　

原题链接：用筛法求之N内的素数

```C++
#include <iostream>

using namespace std;
const int N = 100010;
bool st[N];
int prime[N], cnt;

//朴素筛法，时间最慢
//时间复杂度O(n * ln n)
void normal(int n)
{
    st[0] = st[1] = true;
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) prime[cnt++] = i;
        //筛出每个数的倍数，比如
        //2把4，6，8，10...筛出来
        //3把6，9，12，15...筛出来
        //4把8，12，16，20...筛出来
        for(int j = i + i; j <= n; j += i)
            st[j] = true;
    }
}

//一个埃及人发明的算法，所以叫埃氏筛
//时间复杂度O(n * ln(ln n)), 接近于O(n)
void ai(int n)
{
    st[0] = st[1] = true;
    for(int i = 2; i <= n; i++)
    {
        if(!st[i])
        {
            prime[cnt++] = i;
            //相比朴素筛法唯一不同的是，只是在质数的时候筛出其倍数，
            //这样我们可以发现，不会出现一个数被筛多次的情况
            //例如8被2和4都标记了，使用埃氏筛可以防止这种情况发生
            for(int j = i + i; j <= n; j += i)
                st[j] = true;
        }
    }
}
//欧拉筛，也叫线性筛，很重要的一个算法，是许多其他算法的基础，有必要背下来
//思路是每个数只会被其最小质因子筛掉
//时间复杂度为O(n)
void ola(int n)
{
    st[0] = st[1] = true;
    for(int i = 2; i <= n; i++)
    {
        if(!st[i]) prime[cnt++] = i;
        for(int j = 0; prime[j] <= n / i; j++)
        {
            st[prime[j] *i] = true;
            if(i % prime[j] == 0) break;
        }
    }

}
int main()
{
    int n; cin >> n;
    normal(n);
    //ai(n);
    //ola(n);
    for(int i = 0; i < cnt; i++) 
        cout << prime[i] << endl;
    return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

q浅安时光p

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

1065

校门外的树（C++代码）

C二级辅导-计负均正（C++代码）

用筛法求之N内的素数。 -题解（C++代码）

评论区

精彩推荐

【绝对值排序】（C++代码）（利用两个库函数——abs()求绝对值和 sort()快排）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

不会做的

三角形（C++代码）记忆化搜索

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

A+B for Input-Output Practice （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

1050题解（结构体数组与结构体指针的使用）

Tom数（C语言代码）

q浅安时光p

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题4.9 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

1065

校门外的树 （C++代码）

C二级辅导-计负均正 （C++代码）

用筛法求之N内的素数。 -题解（C++代码）

评论区

精彩推荐

【绝对值排序】 （C++代码）（利用两个库函数——abs()求绝对值 和 sort()快排）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

不会做的

三角形 （C++代码）记忆化搜索

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题8.4 （C语言代码）

A+B for Input-Output Practice （C语言代码）

C语言程序设计教程（第三版）课后习题5.6 （C语言代码）

1050题解（结构体数组与结构体指针的使用）

Tom数 （C语言代码）

校门外的树（C++代码）

C二级辅导-计负均正（C++代码）

　　评论区

【绝对值排序】（C++代码）（利用两个库函数——abs()求绝对值和 sort()快排）

三角形（C++代码）记忆化搜索

Tom数（C语言代码）