Goldbach's conjecture

Goldbach's conjecture is one of the oldest and most famous unsolved problems in number theory and mathematic

What is Goldbach's conjecture?

Every even integer greater than 2 can be written as the sum of two prime numbers.

The conjecture was first proposed in 1742 by the German mathematician Christian Goldbach. In a letter to the renowned mathematician Leonhard Euler, Goldbach suggested that every integer greater than 2 can be written as the sum of three prime numbers. Euler replied, reformulating the conjecture into a simpler and more famous version: Every even integer greater than 2 can be expressed as the sum of two prime numbers.

For example:

4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
20 = 7 + 13

Implementation

#include <bits/stdc++.h>
using namespace std;

void che(bool arr[], int size)
{
    arr[0] = true;
    arr[1] = true;

    for (int i = 2; i * i < size; i++)
    {
        if (arr[i] == true)
            continue;
        for (int j = i * i; j < size; j += i)
        {
            arr[j] = true;
        }
    }
}

int main()
{
    freopen("template.in", "r", stdin);
    freopen("template.out", "w", stdout);

    bool *arr = new bool[1000001];
    che(arr, 1000001);
    int n;
    bool hasAns = false;
    while (cin >> n != EOF)
    {
        if (n == 0) {break;}

        for (int i = 3; i < n; i += 2)
        {
            if (!arr[i] && !arr[n - i])
            {
                hasAns = true;
                printf("%d = %d + %d\n", n, i, n - i);
                break;
            }
        }

        if (!hasAns)
            printf("\nGoldbach's conjecture is wrong.\n");
    }
}