P5736 【深基7.例2】质数筛
题目描述
输入n nn个不大于10 5 10^5105的正整数。要求全部储存在数组中，去除掉不是质数的数字，依次输出剩余的质数。
输入格式
第一行输入一个正整数n nn，表示整数个数。
第二行输入n nn个正整数a i a_iai，以空格隔开。
输出格式
输出一行，依次输出a i a_iai中剩余的质数，以空格隔开。
输入输出样例 #1
输入 #1
5 3 4 5 6 7输出 #1
3 5 7说明/提示
数据保证，1 ≤ n ≤ 100 1\le n\le1001≤n≤100，1 ≤ a i ≤ 10 5 1 \leq a_i \leq 10^51≤ai≤105。
解题思路
题目要求很简单，输入两组数据，分别是一个代表数字个数的整数 n，和 n 个整数。输出一组数字，代表输入数字中所有的质数。
质数的特性是无法被1或自己以外的数整除，这给我们提供了思路，在检测一个数字是否为质数时，我们可以再定义一个变量用作除数，遍历从2到该数字之间的所有数字，如果在数字等于变量之前遇到了可以整除的情况，就说明该数字不是质数。从2开始遍历，是因为1并不是质数，遇到1可以不用测试，直接判定为非质数。
判断逻辑：
//l[i] 是被测试的数字，j 是测试用的除数//外循环：遍历数组for(inti=0;i<n;i++){//内循环：测试是否为质数//如果 l[i] 能被2到 l[i]-1 之间的某个数整除，就不是质数for(j=2;j<l[i];j++){if(l[i]%j==0)break;}接着将数组中，所有非质数位置的数据统一替换为-1（只要是小于1的都可以，题目的数据保证大于等于1），最后输出时只输出质数，跳过所有-1就可以了。
解
#include<stdio.h>intmain(){intn;//数字的数量intj;//测试用的除数scanf("%d",&n);//用输入语句为 n 赋值intl[105];//存输入的数字//用循环为数组赋值for(inti=0;i<n;i++){scanf("%d",&l[i]);}//外循环：遍历数组for(inti=0;i<n;i++){//内循环：测试是否为质数//如果 l[i] 能被2到 l[i]-1 之间的某个数整除，就不是质数for(j=2;j<l[i];j++){if(l[i]%j==0)break;}//将并非质数的位赋值为-1if(l[i]!=j)l[i]=-1;}//用循环输出数组内容for(inti=0;i<n;i++){//如果遇到-1就不输出，只输出有效数据if(l[i]!=-1)printf("%d ",l[i]);}return0;}P5723 【深基4.例13】质数口袋
题目描述
小 A 有一个质数口袋，里面可以装各个质数。他从2 22开始，依次判断各个自然数是不是质数，如果是质数就会把这个数字装入口袋。
口袋的负载量就是口袋里的所有数字之和。
但是口袋的承重量有限，装的质数的和不能超过L LL。给出L LL，请问口袋里能装下几个质数？将这些质数从小往大输出，然后输出最多能装下的质数的个数，数字之间用换行隔开。
输入格式
一行一个正整数L LL。
输出格式
将这些质数从小往大输出，然后输出最多能装下的质数个数。
输入输出样例 #1
输入 #1
100输出 #1
2 3 5 7 11 13 17 19 23 9输入输出样例 #2
输入 #2
5输出 #2
2 3 2输入输出样例 #3
输入 #3
11输出 #3
2 3 5 3说明/提示
数据保证，1 ≤ L ≤ 10 5 1 \le L \le {10}^51≤L≤105。
解题思路
题目要求输入一个数字 L，随后往“口袋”中装入从2开始到该数字之间的所有质数，“口袋”的大小等于 L。最后依次输出口袋中的数字，以及这些数字的数量。
需要注意的是，题目并非只要求输出 L 中包含的使用质数，而是要求依次输出 L 中包含的质数，直到这些质数累加起来的总和超过 L，（并不需要输出导致总和超过 L 的那个数字）最后输出这些质数的数量。
判断逻辑：
//这里 num 是输入的数字（也就是题目中的 L）//j 是测试用的除数，i 是被测试数，all 是“口袋”//外循环：从2开始算，且如果口袋中的内容加上 i 不能超过 num。for(inti=2;all+i<=num;i++){//内循环：除数从2开始//如果 i 能被2到 i-1 之间的某个数整除，说明 i 不是质数//换句话说：我们需要 i 只能被 i 自己整除的情况for(j=2;j<i;j++){if(i%j==0)break;}//如果内循环完整跑完，j 会等于 i//说明2到 i-1 之间没有数能整除 i，即 i 是质数if(j==i){all+=i;//将 i 放进口袋n++;//计数器+1printf("%d\n",i);//输出 i 并换行}}通过all + i <= num这个判断条件，当下一个质数加入口袋时超过了最初输入的 L 时，条件不成立，无法进入下一轮循环，自然也不会出现“口袋”内容“超重”的情况。
依次输出质数，并在最后输出口袋内质数的数量就可以了。
解
#include<stdio.h>intmain(){intnum;//输入的数字，同时也是口袋的承重上限intall=0;//口袋intj;//测质数使用的除数intn=0;//质数的数量scanf("%d",&num);//用输入赋值（别忘了取地址）//外循环：从2开始算，且如果口袋中的内容加上 i 不能超过 num。for(inti=2;all+i<=num;i++){//内循环：除数从2开始//如果 i 能被2到 i-1 之间的某个数整除，说明 i 不是质数//换句话说：我们需要 i 只能被 i 自己整除的情况for(j=2;j<i;j++){if(i%j==0)break;}//如果内循环完整跑完，j 会等于 i//说明2到 i-1 之间没有数能整除 i，即 i 是质数if(j==i){all+=i;//将 i 放进口袋n++;//计数器+1printf("%d\n",i);//输出 i 并换行}}printf("%d\n",n);//最后输出质数数量return0;}另附上该题（质数口袋）的 Java 解：
点击跳转：“洛谷Java题解：分类平均、校门外的树、质数口袋”
