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. Dacă nu se găsește niciun număr cu exact un factor prim, programul afișează NU EXISTA.

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

Cel mai mic numar cu exact un factor prim este: 4

Exemplul 2

Intrare

Introduceti numarul de numere: 10001

Ieșire

Numarul introdus trebuie sa fie intre 1 si 1000!

Rezolvare

<syntaxhighlight lang="python" line>

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

   min_number = float('inf')
   for i in range(n):
       x = int(input("Introduceti numar: "))
       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__':

   n = int(input("Introduceti numarul de numere: "))
   if not validate_input(n):
       print("Numarul introdus trebuie sa fie intre 1 si 1000!")
   else:
       numbers = []
       for i in range(n):
           num = int(input("Introduceti numarul {} din lista: ".format(i+1)))
           numbers.append(num)
       if not validate_numbers(numbers):
           print("Numerele introduse trebuie sa fie mai mici decat 1.000.000.000!")
       else:
           print("Cel mai mic numar cu exact un factor prim este:", 

find_smallest_number_with_one_prime_factor(n))

</syntaxhighlight>