Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- using namespace __gnu_pbds;
- using namespace std;
- #define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>
- typedef long long ll;
- const long long mod = 1000000007;
- ll gcd (ll a, ll b) {return b==0 ? a : gcd(b, a%b);}
- #define all(c) (c).begin(),(c).end()
- #define pb push_back
- #define mp make_pair
- #define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr);
- #define debug_vector(v, n) for(int i = 0; i<n; i++)cout<< v[i] << " \n"[i == n-1]
- #define forn(i, n) for (int i = 0; i < n; i++)
- const int di4[] = {-1, 0, 1, 0};
- const int dj4[] = { 0, 1, 0, -1};
- const int di8[] = {-1, 0, 1, 0, -1, 1,-1,1};
- const int dj8[] = { 0, 1, 0, -1, -1, 1,1,-1};
- struct hash_pair {
- template <class T1, class T2>
- size_t operator()(const pair<T1, T2>& p) const
- {
- auto hash1 = hash<T1>{}(p.first);
- auto hash2 = hash<T2>{}(p.second);
- if (hash1 != hash2) {
- return hash1 ^ hash2;
- }
- return hash1;
- }
- };
- const int maxn = 1000020;
- bool prime[maxn];
- int main()
- {
- #ifdef LOCAL
- freopen("input.txt", "rt", stdin);
- freopen("output.txt", "wt", stdout);
- #endif
- fastio
- auto criba = [&](int n) -> void {
- for (ll i = 0; i <= n; i++)
- prime[i] = 1;
- for (ll p = 2; p * p <= n; p++)
- {
- if (prime[p] == true)
- {
- for (ll i = p * p; i <= n; i += p)
- prime[i] = false;
- }
- }
- prime[1] = prime[0] = 0;
- };
- criba(1000000);
- int n;
- while(cin >> n && n){
- vector<int> primelist, ans;
- for(int i = 2; i<=n; i++){
- if(prime[i])primelist.pb(i);
- }
- unordered_map<int, bool> m;
- auto id = upper_bound(all(primelist), n) - primelist.begin();
- for(int i = 0; i<id; i++){
- m[n - primelist[i]] = true;
- }
- bool ok = false;
- for(int i = 0; i<id; i++){
- if(m[primelist[i]]){
- printf("%d = %d + %d\n",n, primelist[i], n - primelist[i]);
- ok = true;
- break;
- }
- }
- if(!ok)puts("Goldbach's conjecture is wrong.");
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement