鱼C论坛

 找回密码
 立即注册
查看: 2166|回复: 11

[技术交流] 【C++板块提升计划】每周一练 第4期 【代码含注释】

[复制链接]
发表于 2022-9-25 20:49:37 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 zhangjinxuan 于 2023-1-12 21:36 编辑

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

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

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

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

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

样例输入:
  1. 5
  2. 3 4 5 6 7
复制代码


样例输出:
  1. 3 5 7
复制代码


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

程序代码:
  1. #include <cstdio>

  2. using namespace std;

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

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

  18. int main() {
  19.         scanf("%d", &n); //读入长度
  20.         for (int i = 1; i <= n; ++i)
  21.                 scanf("%d", &a[i]); //读入数组
  22.         for (int i = 1; i <= n; ++i)
  23.                 if (is_prime(a[i])) //如果是质数
  24.                         res[++cnt] = a[i]; //加入答案数组
  25.          for (int i = 1; i <= cnt; ++i)
  26.                  printf("%d ", res[i]); //输出答案数组
  27.         return 0;
  28. }
复制代码


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

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2022-9-29 19:26:48 | 显示全部楼层
下一期本人发布



想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-9-25 21:02:11 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-9-25 21:42:35 | 显示全部楼层

不过...
欧拉筛呢
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-9-26 07:12:48 From FishC Mobile | 显示全部楼层
柿子饼同学 发表于 2022-9-25 21:42
不过...
欧拉筛呢

欧拉筛不会...
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-9-26 19:10:49 | 显示全部楼层
@高山
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 (我很着急,人去哪儿了?)

[歌曲乱入,翻译是个人胡乱翻译]
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-9-29 19:18:22 | 显示全部楼层
@元豪 麻烦把上你的第三期上面加上去(末尾):
就像这样:下一期:质数筛
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-9-29 19:19:48 | 显示全部楼层
zhangjinxuan 发表于 2022-9-26 19:10
@高山
Where are you now? (你在哪?)
Atlantis~(高山)

几天不上线,你们就……
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-9-29 19:29:28 | 显示全部楼层
高山 发表于 2022-9-29 19:18
@元豪 麻烦把上你的第三期上面加上去(末尾):
就像这样:下一期:质数筛

OK
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-9-29 20:11:13 | 显示全部楼层
高山 发表于 2022-9-29 19:19
几天不上线,你们就……

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2022-10-14 22:15:19 | 显示全部楼层
建议使用更快的线性筛或欧拉筛算法
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2022-10-15 06:29:50 | 显示全部楼层
ExiaGN001 发表于 2022-10-14 22:15
建议使用更快的线性筛或欧拉筛算法

sorry,不会
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 22:07

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表