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.
