0411 - Prime intre ele 1

Cerinţa

Se dă 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 numar_perechi, reprezentând valoarea dorită.

Restricții și precizări

• n ∈ Ν
• 1 < n ⩽ 1.000

Exemplu1

Intrare

6

Ieșire

Datele de intrare corespund restricțiilor impuse.

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) .

Exemplu2

Intrare

4

Ieșire

Datele de intrare corespund restricțiilor impuse.

6

Explicație

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

Rezolvare

import math


def validare_date(numar):
    flag = False
    if numar.isdigit():
        if 0 < int(numar) < 1_000:
            flag = True
    return flag


def numar_perechi_prime(numar):
    numar_perechi = 0
    for a in range(1, numar+1):
        for b in range(a, numar+1):
            if math.gcd(a, b) == 1:  #verifică dacă numerele a și b sunt prime între ele
                numar_perechi += 1
    print(numar_perechi)


if __name__ == '__main__':
    numar = input()
    if validare_date(numar):
        print("\nDatele de intrare corespund restricțiilor impuse.\n")
        numar_perechi_prime(int(numar))
    else:
        print("Datele de intrare nu corespund restricțiilor impuse.")