笔记
2024-06-01 12:06:39
发布于：广东
11阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
//线性筛出小于等于n的所有质数
void prime(int n,vector<int>& prime){
//使用isprime数组去标记是否为质数
vector<bool> isprime(n+1,true);
isprime[0]=isprime[1]=false;
//标记所有合数（非质数）
for(int p=2;p*p<=n;p++){
if(isprime[p]){
for(int i=p*p;i<=n;i+=p){
isprime[i]=false;
}
}
}
//将所有质数存在prime数组
for(int i=2;i<=n;i++){
if(isprime[i]){
prime.push_back(i);
}
}
}
int main(){
int n;
cin>>n;
vector<int> primes;//生成质数
//遍历所有可能的组合
prime(n,primes);
for(int i=0;i<primes.size();i++){
for(int j=i;j<primes.size();j++){
for(int k=j;k<primes.size();k++){
if(primes[i]+primes[j]+primes[k]==n){
cout<<primes[i]<<" "<<primes[j]<<" "<<primes[k]<<endl;
return 0;
}
}
}
}
return 0;
}
有帮助，赞一个