|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
本帖最后由 zhangjinxuan 于 2023-1-12 21:36 编辑
大家好,今天是每周一练的第4期数期
这次的每周一练由我帮助用户@高山 发帖
题目名称:质数筛
题目说明:
输入 n 个不大于10^5的正整数。要求全部储存在数组中,去除掉不是质数的数字,依次输出剩余的质数。
输入说明:
第一行输入一个正整数 n,表示整数个数。
第二行输入 n 个正整数 a_i,以空格隔开。
输出说明:
输出一行,依次输出 a_i中剩余的质数,以空格隔开。
样例输入:
样例输出:
数据范围:
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;
- }
复制代码
上一篇:求编码值
下一篇:把字符变的一样 |
|