Cerinţa

Se citește un număr natural n, n>1. Să se determine câte perechi (a,b), 1 ≤ a ≤ b ≤ n de numere naturale sunt prime între ele,

Date de intrare

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

Date de ieşire

Programul afișează pe ecran numărul C, reprezentând valoarea dorită.

Restricţii şi precizări

• 1 < n ≤ 1000

Exemplu

Intrare

6

Ieșire

12

Explicație

Perechile sunt: (1 1) (1 2) (1 3) (1 4) (1 5) ( 1 6) (2 3) (2 5) (3 4) (3 5) (4 5) (5 6) .

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

int main()
{
    int n;
    cin >> n;
    int cnt = 0;
    for(int i = 1; i < n; ++i){
        for(int j = i; j <= n; ++j)
        {
            int a = i;
            int b = j;
            while(b){
                int r = a % b;
                a = b;
                b = r;
            }
            if(a == 1)
                cnt++;
        }
    }
    cout << cnt;
    return 0;
}