沉迷枚举选手在线教你极限卡常
思路:
就是暴力枚举四个数,判断它们四个是否有三个以上的数是类质数,是输出YES
和解,不是输出NO
闭着眼睛用脚指头算都知道会TLE
优化
埃氏筛
预处理把质数都算一遍
这种方法更重要:当我们枚举了i,j时,可以先判断i,j是不是类质数,如果都不是,意味着不可能出现l,k使得它们四个数有三个数都是类质数,当枚举到k时同理。
更详细的思路见CODE:
#include<iostream>
typedef unsigned long long ull;
using namespace std;
int n,cnt,m;
bool a[10000001];//a数组用于 存放i是不是质数,是的值为1,不是的值为0
void ass(){//埃氏筛求素数
a[1]=1;//特判,1不是质数
for(int i=2;i*i<=10000000;i++){
if(a[i]==0){
for(int j=i*i;j<=10000000;j+=i){
a[j]=1;//有因数,标记为不是
}
}
}
}
bool jh(int n){//判断类质数
for(int i=2;i*i<=n;i++){
if(n%i==0&&i!=n/i){
if(a[i]==0&&a[n/i]==0) return true; //可以拆成a*(n/i)
}
}
return false;//不符合条件
}
int main(){
ass();
int t;
cin>>t;
while(t--){//多组数据
cin>>n;
int f=0;
int t1,t2,t3,t4;
for(int i=1;i<n;i++){
t1=jh(i);//存储i是不是类质数
for(int j=1+i;j<n;j++){
t2=jh(j);//存储j是不是类质数
if(t1==0&&t2==0) continue;//如果i,j都不是类质数,表示肯定不会存在四个数里面有三个类质数的情况。continue
for(int k=1+j;k<n;k++){
t3=jh(k);//同上
if(t3==0&&t2==0) continue;//同上
int l=n-i-j-k;//优化,直接算出第四个数
t4=jh(l);
if(l>0&&i!=j&&i!=k&&i!=l&&j!=k&&j!=l&&k!=l){//判断是不是有相等的数
int c=t1+t2+t3+t4;//i,j,k,l中的类质数个数
if(c>=3){//符合条件
cout<<"YES\n";//输出YES
f=1;
cout<<i<<' '<<j<<' '<<k<<' '<<l<<endl;
break;//输出解,跳出
}
}
}
if(f==1) break;
}
if(f==1) break;
}
if(f==0) cout<<"NO\n";//没有解,输出NO
}
}