Codeforces A. Captain Flint and Crew Recruitment

Despite his bad reputation, Captain Flint is a friendly person (at least, friendly to animals). Now Captain Flint is searching worthy sailors to join his new crew (solely for peaceful purposes). A sailor is considered as worthy if he can solve Flint’s task.

Recently, out of blue Captain Flint has been interested in math and even defined a new class of integers. Let’s define a positive integer x as nearly prime if it can be represented as p⋅q, where 1<p<q and p and q are prime numbers. For example, integers 6 and 10 are nearly primes (since 2⋅3=6 and 2⋅5=10), but integers 1, 3, 4, 16, 17 or 44 are not.

Captain Flint guessed an integer n and asked you: can you represent it as the sum of 4 different positive integers where at least 3 of them should be nearly prime.

Uncle Bogdan easily solved the task and joined the crew. Can you do the same?

Input
The first line contains a single integer t (1≤t≤1000) — the number of test cases.

Next t lines contain test cases — one per line. The first and only line of each test case contains the single integer n (1≤n≤2⋅105) — the number Flint guessed.

Output
For each test case print:

YES and 4 different positive integers such that at least 3 of them are nearly prime and their sum is equal to n (if there are multiple answers print any of them);
NO if there is no way to represent n as the sum of 4 different positive integers where at least 3 of them are nearly prime.
You can print each character of YES or NO in any case.

题意
对于一个数x，如果它可以表示成x=p×q，称之为近似质数，其中1<p<q，且p,q都为质数。现在给你一个n，请问是否能将这个n分成4个不同的正整数，其中至少3个为近似质数。

题解
至少三个近似质数，那我们就先算出来最小的三个近似质数，分别为6=2×3,10=2×5,14=2×7，只要n>6+10+14，那么它必然可以拆成6,10,14,n−6−10−14，就是符合题意的，所以n<=30直接输出“NO”即可。但是这个时候注意要求不同的正整数，那么也就是要求n−30≠6,n−30≠10,n−30≠14那么出现这种情况怎么办呢？第四大的近似质数是15=3×5,只比14大1。那么出现相等的时候我们就可以将14替换成15，这样n−31必然不会再等于6，10，15。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=2e5+5;
int main()
{
	int n,t;
	cin>>t;
	while(t--)
	{
		int a=6,b=10,c=14,d=15;
		cin>>n;
		if(n<=30)
			cout<<"NO"<<endl;
		else
		{
			int e=n-a-b-c;
			if(e!=a&&e!=b&&e!=c)
			{
				cout<<"YES"<<endl;
				cout<<a<<" "<<b<<" "<<c<<" "<<e<<endl;	
			}	
			else
			{
				cout<<"YES"<<endl;
				cout<<a<<" "<<b<<" "<<d<<" "<<n-a-b-d<<endl; 
			}
		} 
	}
}