Cerința

Se dă un șir a1, a2, …, an format din n numere naturale. Determinați numărul de perechi de elemente din șir (ai,aj) cu i < j, care au suma număr prim.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale, separate prin spații.

Date de ieșire

Programul va afișa pe ecran numărul rezultatelor care sunt numere prime.

Restricții și precizări

• 2 ≤ n ≤ 100.000
• elementele șirului vor fi mai mici decât 10.000

Exemplu

Intrare

3
2 5 9

Ieșire

2

Explicație

Sumele obţinute sunt 2+5=7 , 2+9=11 , 5+9=14. Dintre rezultatele obţinute, două sunt prime, 7 şi 11.

#include <bits/stdc++.h>
using namespace std;
int main()
{
    std::ios::sync_with_stdio(false);
    int n , E[20001]={0} , max = 20000;
    unsigned long long c = 0,F[10001]={0};
    for(int i = 2 ; i <= max ; i++)
        E[i] = 1;
    for(int i = 2 ; i * i <= max; i++)
        if(E[i] == 1)
            for(int j = i * i ; j <= max ; j= j + i)
                E[j] = 0;
    cin >> n;
    for(int i = 1 ; i <= n ; i++)
    {
        int x;
        cin >> x;
        F[x]++;
    }
    c += F[1]*(F[1]-1)/2;
    c += F[0]*F[2];
    for(int i = 1 ; i <= 10000 ; i = i + 2)
        if(F[i] != 0)
            for(int j = i + 1 ; j <= 10000 ; j = j + 2)
                if(F[j] != 0)
                    if(E[i+j] == 1) c += F[i]*F[j];
    for(int i = 0 ; i <= 10000 ; i = i + 2)
        if(F[i] != 0)
            for(int j = i + 1 ; j <= 10000 ; j = j + 2)
                if(F[j] != 0)
                    if(E[i+j] == 1) c += F[i]*F[j];
    cout<<c;
    return 0;
}