3355 - Caramele

Sursa: [1]

Cerinţa

Se dau n numere naturale. Determinați cel mai mic număr care are un singur factor prim. Dacă nu există niciun număr cu un singur factor prim se va afișa mesajul NU EXISTA.

Date de intrare

Programul citește de la tastatură numărul n, iar apoi n numere naturale.

Date de ieșire

Acest program primește ca input un număr n și o listă de n numere. Scopul său este de a găsi cel mai mic număr din listă care are exact un factor prim.

Dacă numărul are exact un factor prim și este mai mic decât cel mai mic număr găsit până acum, acesta este actualizat ca fiind cel mai mic număr, iar în consolă va fi afișat mesajul "Datele introduse corespund cerintelor." Dacă nu se găsește niciun număr cu exact un factor prim, programul afișează NU EXISTA, iar în cazul în care datele sunt introduse greșit programul va afișa "Datele introduse nu corespund cerintelor."

Restricţii şi precizări

• 1 ⩽ n ⩽ 1000
• cele n numere citite vor fi mai mici decât 1.000.000.000.

Exemplul 1

Intrare

Introduceti numarul de numere: 5

Introduceti numar: 12

Introduceti numar: 9

Introduceti numar: 16

Introduceti numar: 4

Introduceti numar: 20

Ieșire

Datele introduse corespund cerintelor

4

Exemplul 2

Intrare

Introduceti numarul de numere: 10001

Ieșire

Datele introduse nu corespund cerintelor.

Rezolvare

#3355
import math

def has_only_one_prime_factor(n):
    d, cnt = 2, 0
    while n > 1:
        p = 0
        while n % d == 0:
            n //= d
            p += 1
        if p:
            cnt += 1
        d += 1
        if d * d > n:
            d = n
    return cnt == 1


def find_smallest_number_with_one_prime_factor(n, numbers):
    min_number = float('inf')
    for i in range(n):
        x = numbers[i]
        if has_only_one_prime_factor(x) and x < min_number:
            min_number = x
    if min_number < float('inf'):
        return min_number
    else:
        return "NU EXISTA"


def validate_input(n):
    if n < 1 or n > 1000:
        return False
    return True


def validate_numbers(numbers):
    for num in numbers:
        if num >= 1000000000:
            return False
    return True


if __name__ == '__main__':
    numbers = []
    n = int(input("Introduceti numarul de numere: "))
    if not validate_input(n):
        print("Datele introduse nu corespund cerintelor.")
    else:
        for i in range(n):
            num = int(input("Introduceti numarul {} din lista: ".format(i+1)))
            numbers.append(num)
        if not validate_numbers(numbers):
            print("Datele introduse nu corespund cerintelor.")
        else:
            print("Datele introduse corespund cerintelor\n",find_smallest_number_with_one_prime_factor(n, numbers))

Explicatie rezolvare

Acest program determină cel mai mic număr dintre o listă de numere care are un singur factor prim. Programul primește numărul de numere pe care utilizatorul dorește să le introducă, apoi citește aceste numere și verifică dacă fiecare dintre acestea are un singur factor prim. Dacă un număr îndeplinește această condiție și este mai mic decât cel mai mic număr găsit până acum, acesta devine noul cel mai mic număr. Dacă nu există niciun număr cu un singur factor prim, programul returnează NU EXISTA.

Funcția has_only_one_prime_factor(n) este folosită pentru a verifica dacă un număr are un singur factor prim. Aceasta folosește o metodă de divizare repetată, pornind de la 2 și incrementând cu 1 în fiecare iterație. În fiecare iterație, programul împarte numărul la divizorul curent până când nu mai poate fi împărțit, numărând de asemenea de câte ori a putut fi împărțit numărul cu divizorul curent. Dacă numărul a putut fi împărțit cel puțin o dată, se adaugă 1 la numărul de factori primi ai numărului, dacă nu se trece la următorul divizor. Procesul se repetă până când divizorul ridicat la pătrat depășește numărul verificat, caz în care numărul verificat trebuie să fie ultimul factor prim, sau numărul verificat devine 1, caz în care s-a terminat divizarea.

Funcția find_smallest_number_with_one_prime_factor(n) primește un număr n, apoi citește n numere de la tastatură și verifică dacă fiecare dintre acestea are un singur factor prim. Dacă un număr îndeplinește această condiție și este mai mic decât cel mai mic număr găsit până acum, acesta devine noul cel mai mic număr. Funcția returnează cel mai mic număr găsit cu un singur factor prim sau NU EXISTA dacă niciun număr din listă nu îndeplinește această condiție.

Funcțiile validate_input(n) și validate_numbers(numbers) sunt folosite pentru a verifica dacă numărul de numere introdus și numerele introduse îndeplinesc anumite condiții. Funcția validate_input(n) verifică dacă numărul de numere este între 1 și 1000, iar funcția validate_numbers(numbers) verifică dacă toate numerele din listă sunt mai mici decât 1.000.000.000.