洛谷 P5723 【深基4.例13】质数口袋 题解

题面传送门

观察题目，我们可以看到这是一道朴素的，判断质数的一道题目。

何为质数？质数就是除了 1 1 1 和这个本身，没有其他因数的数。特别的， 1 1 1 和 0 0 0 既不是质数也不是合数。

很容易就可以得到以下判断质数的代码。

bool is_pri(long long x){
	if(x==0||x==1){
		return false;//特判
	}
	for(long long i=2;i<=x-1;i++){
		if(x%i==0){
			return false;
		}
	}
	return true;
}

但是，这样会有 O ( n ) O(n) O(n) 的时间复杂度，对于更高的数据限制，很明显是吃不消的。经过思考可得，我们还可以只判断到 n 2 \dfrac{n}{2} 2n​ 即可。于是便有了以下代码。

bool is_pri(long long x){
	if(x==0||x==1){
		return false;//特判
	}
	for(long long i=2;i<=x/2;i++){
		if(x%i==0){
			return false;
		}
	}
	return true;

这样还是很慢。怎么办呢？我们还有一种 O ( n ) O(\sqrt n) O(n ​) 的方法，只需遍历到 ⌈ n ⌉ \left\lceil\sqrt n\right\rceil ⌈n ​⌉。解释：如果一个数不是质数就是合数（ 1 1 1 和 0 0 0 除外），那么一定可以由两个自然数相乘得到，其中一个大于或等于它的平方根，一个小于或等于它的平方根，并且成对出现。

综上所述，就可以得到以下代码。

bool is_pri(long long x){
	if(x==0||x==1){
		return false;
	}
	for(long long i=2;i*i<=x;i++){//换了一种方式
		if(x%i==0){
			return false;
		}
	}
	return true;
}

接下来再来实现主函数代码。由题意分析可得，这道题应采用循环结构，用 while 循环来实现。如果重量超过了袋子的负载量，就结束。

以下是 while 循环的代码。

	while(1){
		if(is_pri(j)){
			if(now+j>l){//now 是用来存储当前袋子的重量的
				break;
			}
			cout<<j<<endl;
			ans++;
			now+=j;
		}
		j++;
	}

以下来看详细代码（时间复杂度粗略估计为 O ( l l ln ⁡ l ) O(l \sqrt{\frac{l}{\ln l}}) O(llnll​ ​)）。

#include<bits/stdc++.h>
using namespace std;
long long l,now=0,ans=0,j=2;
bool is_pri(long long x){
	if(x==0||x==1){
		return false;
	}
	for(long long i=2;i*i<=x;i++){
		if(x%i==0){
			return false;
		}
	}
	return true;
}
int main(){
	cin>>l;
	while(1){
		if(is_pri(j)){
			if(now+j>l){
				break;
			}
			cout<<j<<endl;
			ans++;
			now+=j;
		}
		j++;
	}
	cout<<ans<<endl;
	return 0;
}