解题思路
查看原帖
解题思路
610059
lingzhuohua666楼主2021/11/14 19:44

解题思路:

首先,明确几个变量。

1.L,即输入的数; 2.承重量,即所有输出的质数的和不能超过承重量,一旦求得的质数之和大于承重量,我们就不需要再判断下一个数是否为质数了,因为装不下了。到这里,想想,我们是否有了一个思路是用for循环判断质数呢,承重量有限,我们只需要一个break语句,终止整个循环。 3.能装下的质数的个数。是不是想起了我们习惯用的计数cnt++呢?

接下来,是真正的解题思路啦:

我们判断一个数是否为质数,如果是质数,则把这个质数加到承重量里,注意,一开始承重量为0;然后计数一个有多少个质数,每有一个质数,cnt++,同时输出该质数;每判断出一个质数后,都要判断目前的承重量是否超出题目的承重量,也就是L,超出则终止所有循环,输出一个计数cnt。

以下为解题代码:

#include<iostream>
using namespace std;

int main()
{
	int L,load=0,cnt=0;//定义输入的L,承重量,质数的个数 
	cin>>L;//输入一个数,也就是承重量 
	for(int i=2;;i++)//判断i是否为质数 ,第一个;后面为什么时候执行该循环,因为承重量超过L时不执行循环,这个语句暂不写,我们再后面给出一个条件是什么时候跳出该循环 
	{
		int is_prime=1;
		for(int j=2;j*j<=i;j++)//我们不需要枚举1到i的所有数,只需要枚举到i的平方根即可 
		{
			if(i%j==0)
			is_prime=0;//如果i能整除小于i的平方根的任何一个数,说明i不是质数 
		}
		if(!is_prime) continue;//如果i不是质数,结束本轮循环,进入下一轮,即判断i+1是否为质数
		if(load+i>L) break;//如果所有质数之和大于L,即超出承重量,结束整个循环,不再判断其他质数,因为装不下了
		cout<<i<<endl;//每发现一个质数,就输出一个质数 
		load+=i;//承重量在一点一点增加 
		cnt++; //计数:到目前为止有多少个质数 
	}
	cout<<cnt<<endl;
	return 0;
}
2021/11/14 19:44
加载中...