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_back typedef long long ll; typedef pair<ll, ll> ii; typedef vector< int > vi; typedef long double ld; #define mod 1000000007 const 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) 이지만 괜찮아
|