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

Explicație

Programul verifică dacă un număr dat respectă restricțiile impuse și calculează numărul de perechi de numere prime între ele, mai mici sau egale cu numărul dat, utilizând o buclă dublă. Pentru a determina dacă două numere sunt prime între ele, se folosește funcția math.gcd() din Python, care calculează cel mai mare divizor comun al acestora și verifică dacă acesta este egal cu 1. La final, numărul de perechi de numere prime între ele este afișat.