1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
| #include <iostream> // standard input & output cout cin#include <cstdio> // scanf printfsssss#include <vector> // std::vector#include <algorithm>#include <string> // std::string#include <queue> // std::queue#include <cstring> // memset#include <set> // std::set#include <utility> // std::pair, std::make_pair#include <map>#include <list>#include <stack>#include <deque>#include <cmath>#include <climits>#include <cassert>using namespace std;#define fi first#define se second#define mp make_pair#define pb push_backtypedef long long ll;typedef pair<ll, ll> ii;typedef vector<int> vi;typedef long double ld;#define mod 1000000007const char newline = '\n';ll powmod(ll a, ll b) {ll res=1; a %= mod; assert(b >= 0); for(; b; b >>= 1) {if (b & 1) res = res * a % mod; a = a * a % mod;} return res;}const int MAX_N = 1001;int n = 1001;bool isPrime[MAX_N];void eratosthenes(){ memset(isPrime, 1, sizeof(isPrime)); isPrime[0] = isPrime[1] = false; int sqrtn = int(sqrt(n)); for(int i = 2; i <= sqrtn; i++) { if(isPrime[i]) { for(int j = i*i ; j <= n ;j+=i) { isPrime[j] = false; } } }}int main(int argc, char **argv){ ios_base::sync_with_stdio(false); cin.tie(0); int t; vector<int> primes; eratosthenes(); for(int i = 0 ; i < MAX_N ; i++) { if(isPrime[i]) primes.pb(i); } cin>>t; while(t--) { int K; int done = 0; cin>>K; for(int i = 0; i<primes.size() ;i++) { if(done) break; for(int j = i ; j < primes.size() ;j++) { if(done) break; for(int k = j ; k < primes.size(); k++) { if(done) break; if(primes[i] + primes[j] + primes[k] == K) { cout<<primes[i]<<' '<<primes[j]<<' '<<primes[k]<<newline; done = 1; } } } } } return 0;}
O(N^3) 이지만 괜찮아
|