fork(1) download
copy 
  1. #include <iostream>
  2. #include <fstream>
  3. #include <math.h>
  4. #include <bitset>
  5. #include <vector>
  6. using namespace std;
  7.  
  8. /* Prime Number */
  9.  
  10. #define SIZE 1000000LL
  11. bitset<SIZE+1> prime;
  12. vector<int> gpf;
  13.  
  14. void sieve()
  15. {
  16.         int sq = ceil(sqrt(SIZE));
  17.         for(int i = 2; i <= sq; ++i)
  18.         {
  19.                 if(!prime.test(i))
  20.                 {
  21.                         for(int j = i*i; j <= SIZE; j += i)
  22.                                 prime.set(j,1);
  23.                 }
  24.         }
  25.  
  26.         for(int i = 2;i <= SIZE; ++i)
  27.         {
  28.                 if(!prime.test(i))
  29.                         gpf.push_back(i);
  30.         }
  31. }
  32.  
  33. bool is_sieve_prime(int num)
  34. {
  35.         return !prime.test(num);
  36. }
  37.  
  38. int main()
  39. {
  40.  
  41.         sieve();
  42.         int num;
  43.  
  44.         while( cin >> num )
  45.         {
  46.                 if(!num)
  47.                         break;
  48.                 if( num < 4 )
  49.                 {
  50.                         printf("Goldbach's conjecture is wrong.\n");
  51.                         continue;
  52.                 }
  53.  
  54.                 vector<int>::iterator it;
  55.                 bool found = false;
  56.                 int sq = ceil(sqrt(num));
  57.                 for(it = gpf.begin(); (it != gpf.end() && *it <= sq); ++it)
  58.                 {
  59.                         int p = *it;
  60.                         if(is_sieve_prime(num-p))
  61.                         {
  62.                                 printf("%d = %d + %d\n", num, p, (num - p));
  63.                                 found = true;
  64.                                 break;
  65.  
  66.                         }
  67.                 }
  68.                 if(!found)
  69.                         printf("Goldbach's conjecture is wrong.\n");
  70.         }
  71.         return 0;
  72. }
  73.  
Success #stdin #stdout 0.02s 2936KB
comments (?)
stdin
copy 
8
20
42
999998
14372
50
6
2
4
100
10000
999
999997
0
stdout
copy 
8 = 3 + 5
20 = 3 + 17
42 = 5 + 37
999998 = 19 + 999979
14372 = 3 + 14369
50 = 3 + 47
6 = 3 + 3
Goldbach's conjecture is wrong.
4 = 2 + 2
100 = 3 + 97
10000 = 59 + 9941
999 = 2 + 997
Goldbach's conjecture is wrong.
https://ideone.com/dR8w5y
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
secret

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!