【C++板块提升计划】每周一练 第4期 【代码含注释】

zhangjinxuan

大家好，今天是每周一练的第4期数期

这次的每周一练由我帮助用户@高山 发帖
题目名称：质数筛

题目说明：
输入 n 个不大于10^5的正整数。要求全部储存在数组中，去除掉不是质数的数字，依次输出剩余的质数。

输入说明：
第一行输入一个正整数 n，表示整数个数。
第二行输入 n 个正整数 a_i，以空格隔开。

输出说明：
输出一行，依次输出 a_i中剩余的质数，以空格隔开。

样例输入：

5
3 4 5 6 7

样例输出：

3 5 7

数据范围：
1 <= n <= 100
1 <= a_i <= 10^5

程序代码：

#include <cstdio>

using namespace std;

char prime_numbers[100001] = {-1, -1}; //定义一个数组，prime_numbers[i]（prime_numbers以下简称p)等于-1表示非质数，等于1表示质数，等于0表示未求出
/*注：使用char为了节省空间，并且数组大小要开10^5+1,不然p[100000]会越界*/
int n, x, a[100001]; //定义所需变量，数组 
int res[100001], cnt = 0; // 答案数组

bool is_prime(int num) {
        if (prime_numbers[num] == 0) { //如果p[i]等于0，说明没有求出，得先求出答案，再更新p数组
                for (int i = 2; i * i <= num; ++i) //从2开始枚举
                        if (num % i == 0) { //不是质数
                                prime_numbers[num] = -1; //更新答案
                                return 0; //返回假
                        }
                return prime_numbers[num] = 1; //更新答案，并且返回真
        }
        return prime_numbers[num] == 1; //如果p[i]不等于0，说明前面已经算过了，判断一下即可
}

int main() {
        scanf("%d", &n); //读入长度
        for (int i = 1; i <= n; ++i) 
                scanf("%d", &a[i]); //读入数组 
        for (int i = 1; i <= n; ++i)
                if (is_prime(a[i])) //如果是质数 
                        res[++cnt] = a[i]; //加入答案数组 
         for (int i = 1; i <= cnt; ++i) 
                 printf("%d ", res[i]); //输出答案数组
        return 0;
}

上一篇：求编码值
下一篇：把字符变的一样

高山

下一期本人发布

演示视频请戳我

hveagle

@高山

柿子饼同学

不过...
欧拉筛呢

zhangjinxuan

柿子饼同学 发表于 2022-9-25 21:42
不过...
欧拉筛呢

欧拉筛不会...

zhangjinxuan

@高山
Where are you now? (你在哪？）
Atlantis~（高山）
Under the sea? （在潜水吗？）
Under the sea~e （不在线吗？）
Where are you now? （你在哪儿？）
Another dream~ （又一天过去了）
The monsters running wild inside of me （着急在我身体内狂奔）
I'm faded （我很着急）
I'm faded （我很着急）
So lost （我十分着急）
I'm faded （我很着急，人去哪儿了？）

[歌曲乱入,翻译是个人胡乱翻译]

高山

@元豪 麻烦把上你的第三期上面加上去（末尾）：
就像这样：下一期：质数筛

高山

zhangjinxuan 发表于 2022-9-26 19:10
@高山
Where are you now? (你在哪？）
Atlantis~（高山）

几天不上线，你们就……

元豪

高山 发表于 2022-9-29 19:18
@元豪 麻烦把上你的第三期上面加上去（末尾）：
就像这样：下一期：质数筛

OK

zhangjinxuan

高山 发表于 2022-9-29 19:19
几天不上线，你们就……

ExiaGN001

建议使用更快的线性筛或欧拉筛算法

zhangjinxuan

ExiaGN001 发表于 2022-10-14 22:15
建议使用更快的线性筛或欧拉筛算法

sorry，不会