【C++板块提升计划】每周一练 第4期 【代码含注释】
本帖最后由 zhangjinxuan 于 2023-1-12 21:36 编辑大家好，今天是每周一练的第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 = {-1, -1}; //定义一个数组，prime_numbers（prime_numbers以下简称p)等于-1表示非质数，等于1表示质数，等于0表示未求出
/*注：使用char为了节省空间，并且数组大小要开10^5+1,不然p会越界*/
int n, x, a; //定义所需变量，数组
int res, cnt = 0; // 答案数组
bool is_prime(int num) {
if (prime_numbers == 0) { //如果p等于0，说明没有求出，得先求出答案，再更新p数组
for (int i = 2; i * i <= num; ++i) //从2开始枚举
if (num % i == 0) { //不是质数
prime_numbers = -1; //更新答案
return 0; //返回假
}
return prime_numbers = 1; //更新答案，并且返回真
}
return prime_numbers == 1; //如果p不等于0，说明前面已经算过了，判断一下即可
}
int main() {
scanf("%d", &n); //读入长度
for (int i = 1; i <= n; ++i)
scanf("%d", &a); //读入数组
for (int i = 1; i <= n; ++i)
if (is_prime(a)) //如果是质数
res[++cnt] = a; //加入答案数组
for (int i = 1; i <= cnt; ++i)
printf("%d ", res); //输出答案数组
return 0;
}
上一篇：求编码值
下一篇：把字符变的一样 下一期本人发布
演示视频请戳我
@高山 {:10_275:}
不过...
欧拉筛呢 柿子饼同学 发表于 2022-9-25 21:42
不过...
欧拉筛呢
欧拉筛不会... @高山
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 高山 发表于 2022-9-29 19:19
几天不上线，你们就……
{:5_109:} 建议使用更快的线性筛或欧拉筛算法 ExiaGN001 发表于 2022-10-14 22:15
建议使用更快的线性筛或欧拉筛算法
sorry，不会{:10_266:}
页:
[1]