Advertisement
pedrocasdev

Untitled

Sep 9th, 2022
55
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.13 KB | None | 0 0
  1.  
  2. #include <bits/stdc++.h>
  3. #include <ext/pb_ds/assoc_container.hpp>
  4. #include <ext/pb_ds/tree_policy.hpp>
  5. using namespace __gnu_pbds;
  6. using namespace std;
  7.  
  8. #define ordered_set tree<pair<int, int>, null_type,less<pair<int, int>>, rb_tree_tag,tree_order_statistics_node_update>
  9. typedef long long ll;
  10. const long long mod = 1000000007;
  11. ll gcd (ll a, ll b) {return b==0 ? a : gcd(b, a%b);}
  12.  
  13. #define all(c) (c).begin(),(c).end()
  14. #define pb push_back
  15. #define mp make_pair
  16. #define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr);
  17. #define debug_vector(v, n) for(int i = 0; i<n; i++)cout<< v[i] << " \n"[i == n-1]
  18. #define forn(i, n) for (int i = 0; i < n; i++)
  19.  
  20. const int di4[] = {-1, 0, 1,  0};
  21. const int dj4[] = { 0, 1, 0, -1};
  22. const int di8[] = {-1, 0, 1,  0, -1, 1,-1,1};
  23. const int dj8[] = { 0, 1, 0, -1, -1, 1,1,-1};
  24. struct hash_pair {
  25.     template <class T1, class T2>
  26.     size_t operator()(const pair<T1, T2>& p) const
  27.     {
  28.         auto hash1 = hash<T1>{}(p.first);
  29.         auto hash2 = hash<T2>{}(p.second);
  30.  
  31.         if (hash1 != hash2) {
  32.             return hash1 ^ hash2;
  33.         }
  34.  
  35.          return hash1;
  36.     }
  37. };
  38.  
  39. const int maxn = 1000020;
  40. bool prime[maxn];
  41. int main()
  42. {
  43. #ifdef LOCAL
  44.     freopen("input.txt", "rt", stdin);
  45.     freopen("output.txt", "wt", stdout);
  46. #endif
  47.     fastio
  48.    
  49.     auto criba = [&](int n) -> void {
  50.         for (ll i = 0; i <= n; i++)
  51.           prime[i] = 1;
  52.         for (ll p = 2; p * p <= n; p++)
  53.         {
  54.           if (prime[p] == true)
  55.           {
  56.             for (ll i = p * p; i <= n; i += p)
  57.               prime[i] = false;
  58.           }
  59.         }
  60.         prime[1] = prime[0] = 0;
  61.     };
  62.     criba(1000000);
  63.     int n;
  64.     while(cin >> n  && n){
  65.         vector<int> primelist, ans;
  66.         for(int i = 2; i<=n; i++){
  67.             if(prime[i])primelist.pb(i);
  68.         }
  69.         unordered_map<int, bool> m;
  70.         auto id = upper_bound(all(primelist), n) - primelist.begin();
  71.         for(int i = 0; i<id; i++){
  72.             m[n - primelist[i]] = true;
  73.         }
  74.         bool ok = false;
  75.         for(int i = 0; i<id; i++){
  76.             if(m[primelist[i]]){
  77.                 printf("%d = %d + %d\n",n, primelist[i], n - primelist[i]);
  78.                 ok = true;
  79.                 break;
  80.             }
  81.         }
  82.         if(!ok)puts("Goldbach's conjecture is wrong.");
  83.     }
  84.     return 0;
  85. }
  86.  
  87.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement