Cerința

Se dă un număr natural n, par, mai mare decat 2. Scrieţi-l pe n ca sumă de 2 numere prime în toate modurile posibile.

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa perechile p q de numere prime, în ordine crescătoare după q, câte o pereche pe fiecare rând.

Restricții și precizări

• 2 ≤ n < 11.111.111
• n % 2 = 0

Exemplu

Intrare

98

Ieșire

19 79
31 67
37 61
61 37
67 31
79 19

Explicație

Perechile sunt : 19 79, 31 67, 37 61, 61 37, 67 31, 79 19.

#include <bits/stdc++.h>
using namespace std;
#define NN 11111111
int v[NN + 1];
int main()
{
    int n;
    cin >> n;
    v[0] = v[1] = 1;
    for(int i = 2 ; i * i <= n ; i ++)
        if(v[i] == 0)
            for(int j = 2 ; i * j <= n ; j ++)
                v[i * j] = 1;
    for(int i = 2 ; i <= n - 2 ; i ++)
        if(v[i] == 0 && v[n-i] == 0)
            cout << i << " " << n - i <<endl;
    return 0;
}