3278 - AproapePrime

Cerinţa

Spunem că un număr natural este aproape prim dacă el poate fi scris ca produs de două numere prime. De exemplu 6 și 25 sunt aproape prime pentru că 6 = 2 * 3, iar 25 = 5 * 5. Considerăm șirul crescător al numerelor naturale aproape prime: 4, 6, 9, 10, 14, 15, 21, … Acestora li se asociază câte un număr de ordine, numerotarea începând cu 1. Deci 4 este primul număr aproape prim, 6 este al doilea număr, 9 este al treilea etc. Dat un număr natural N, să se determine al N-lea număr aproape prim.

Date de intrare

Programul citește de la tastatură numărul N.

Date de ieșire

Dacă datele sunt introduse corect, pe ecran se va afișa pe ecran un singur număr natural, reprezentând al N-lea număr aproape prim. În caz contrar, se va afișa pe ecran: "Datele nu sunt comform restricțiilor impuse.".

Restricţii şi precizări

1 ≤ N ≤ 23.378

Exemple

Exemplul 1

Intrare: 4
Ieșire: Datele sunt corecte.; 10

Exemplul 2

Intrare: 5
Ieșire: Datele sunt corecte.; 14

Exemplul 3

Intrare: 314515341535441
Ieșire: Datele nu sunt comform restricțiilor impuse.

Rezolvare

3278 AproapePrim

def este_prim(n):

   if n < 2:
       return False
   for i in range(2, int(n ** 0.5) + 1):
       if n % i == 0:
           return False
   return True

def aproape_prim(N):

   contor = 0
   i = 2
   while True:
       if contor == N:
           return i-1
       if este_prim(i):
           i += 1
           continue
       for j in range(2, int(i ** 0.5) + 1):
           if i % j == 0 and este_prim(j) and este_prim(i // j):
               contor += 1
               break
       i += 1

def conform_restrictiilor():

   N = int(input())
   if not 1 <= N <= 23378:
       print("Datele nu sunt conform restricțiilor impuse.")
       exit()
   print("Datele sunt corecte.")
   return N

if __name__ == '__main__':

   N = conform_restrictiilor()
   print(aproape_prim(N))

</syntaxhighlight>

Explicaţie cod

Funcția este_prim(n) primește un număr întreg n și returnează True dacă acesta este prim și False altfel. Ea verifică dacă numărul este mai mic decât 2 (în acest caz, nu este prim) și apoi verifică dacă există vreun divizor între 2 și radicalul pătrat al lui n (inclusiv) care îl divide pe n. Dacă există, numărul nu este prim.

Funcția aproape_prim(N) primește un număr întreg N și returnează al N-lea număr aproape prim din șirul de numere aproape prime. Ea inițializează un contor de indexare cu 0 și i cu 2. Apoi, începe să itereze prin numerele naturale, verificând dacă fiecare număr este aproape prim. Dacă un număr este prim, continuă iterația cu următorul număr, astfel încât numai numerele compuse sunt testate pentru a fi aproape prime. Pentru a verifica dacă un număr este aproape prim, programul încearcă să îl descompună în factori primi și să verifice dacă ambele sunt prime. Dacă da, crește contorul cu 1 și trece la următorul număr. Când contorul ajunge la N, programul returnează ultimul număr testat minus 1, deoarece ultimul număr a fost al N-lea număr aproape prim.

Funcția conform_restrictiilor() primește noul număr întreg N de la tastatură și verifică dacă este între 1 și 23378, conform restricțiilor impuse. Dacă nu este, afișează un mesaj de eroare și încheie programul cu funcția exit(). Dacă este corect, afișează un mesaj de confirmare și returnează valoarea.

În funcția principală, programul citește N și apoi apelează funcția aproape_prim(N) și afișează rezultatul returnat.