fork download
copy 
  1. // Sieve of Etaros O(nloglogn)
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. const int N = 1000000;
  6. vector<int> prime;
  7. vector<bool> check(N);
  8. void Eratos() {
  9.     check[0] = check[1] = true;
  10.  
  11.     for (int i = 2; i < N; i += 2) check[i] = true;
  12.  
  13.     for (int i = 3; i < N; ++i)
  14.         if (!check[i]) {
  15.             prime.push_back(i);
  16.             for (int j = i * 2; j < N; j += i) check[j] = true;
  17.         }
  18. }
  19.  
  20. int main(void) {
  21.     cin.tie(nullptr)->sync_with_stdio(false);
  22.     Eratos();
  23.     int n, size = prime.size();
  24.     while (cin >> n, n) {
  25.         for (int i = 0; i < size; ++i) {
  26.             int res = n - prime[i];
  27.  
  28.             if (prime[i] > res) break;
  29.  
  30.             if (!check[res]) {
  31.                 cout << n << " = " << prime[i] << " + " << res << '\n';
  32.                 goto end;
  33.             }
  34.         }
  35.         cout << "Goldbach's conjecture is wrong.\n";
  36.     end:;
  37.     }
  38. }
  39.  
Success #stdin #stdout 0.01s 5344KB
comments (?)
stdin
copy 
8
20
42
0
stdout
copy 
8 = 3 + 5
20 = 3 + 17
42 = 5 + 37
https://ideone.com/3tuCtn
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!