2576 - Ciurul Lui Eratosthenes

Sursa: - Ciurul Lui Eratosthenes

---

Cerinţa

Să se afișeze numerele prime de la 1 la n.

Date de intrare

Se citește numărul n.

Date de ieșire

Se vor afișa numerele prime de la 1 la n, în ordine crescătoare,separate printr-un spațiu iar pe ecran se va afisa "Datele sunt corecte." dar daca n < 2 se va afisa pe un rand nou "Nu exista numere prime mai mici decat 2.". In caz contrar, se va afisa "Datele nu sunt comform restricțiilor impuse.".

Restricţii şi precizări

• 1 ≤ n ≤ 1.000.000

Exemple

Exemplul 1

Intrare

30

Ieșire

Datele sunt corecte.

2 3 5 7 11 13 17 19 23 29

Exemplul 2

Intrare

2

Ieșire

Datele sunt corecte.

Nu exista numere prime mai mici decat 2.

Exemplul 3

Intrare

154242352352

Ieșire

Datele nu sunt comform restricțiilor impuse.

Rezolvare

<syntaxhighlight lang="python" line>

1. 2576 Ciurul Lui Eratosthenes

def ciur(n):

   if n < 2:
       print("Nu exista numere prime mai mici decat 2.")
   else:
       prime = []
       for i in range(2, n+1):
           e_prim = True
           for j in range(2, int(i ** 0.5) + 1):
               if i % j == 0:
                   e_prim = False
                   break
           if e_prim:
               prime.append(i)
       print(*prime)
   
       

def conform_restrictiilor():

   n = int(input())
   if n > 1000000 or n < 1:
       print("Datele nu sunt comform restricțiilor impuse.")
       exit()
   print("Datele sunt corecte.")
   return n

if __name__ == '__main__':

   n = conform_restrictiilor()
   ciur(n)

</syntaxhighlight>

Explicaţie cod

Citim valoarea lui n de la tastatură și o convertim într-un număr întreg utilizând funcția int(). Verificăm dacă n este mai mic decât 2. Dacă da, afișăm un mesaj corespunzător și nu facem nimic altceva. Dacă nu, continuăm. Inițializăm o listă goală pentru a stoca numerele prime. Parcurgem toate numerele de la 2 la n folosind o buclă for. Verificăm dacă fiecare număr este prim folosind o altă buclă for. Pentru a verifica dacă un număr este prim, împărțim acest număr la toate numerele întregi de la 2 la radicalul său pătrat și verificăm dacă are vreun divizor întreg. Dacă găsim un divizor, înseamnă că numărul nu este prim și ieșim din bucla internă cu ajutorul instrucțiunii break. Dacă nu găsim niciun divizor, înseamnă că numărul este prim și îl adăugăm la lista de numere prime. La sfârșit, afișăm lista de numere prime utilizând operatorul de expansiune * pentru a transforma lista într-o serie de argumente separate prin spațiu în funcția print().