Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-03-10 11:16:42.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:ciur.in, ciur.outSursăad-hoc
AutorArhiva EducationalaAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.05 secLimită de memorie7168 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Ciurul lui Eratosthenes

Spunem ca un numar natural x este prim daca si numai daca x > 1 si singurii sai divizori sunt 1 si x.

Cerinta

Dandu-se un numar natural N, sa se determine numarul numerelor prime mai mici sau egale cu N.

Date de intrare

Fisierul de intrare ciur.in contine o singura linie pe care se afla numarul N.

Date de iesire

In fisierul de iesire ciur.out se va scrie pe prima linie raspunsul cerut.

Restrictii

  • 2 ≤ N ≤ 2 000 000

Exemplu

ciur.inciur.out
104

Indicatii de rezolvare

Sift the Two's and sift the Three's, The Sieve of Eratosthenes. When the multiples sublime, The numbers that remain are Prime. :)

O rezolvare imediata ar fi iterarea tuturor numerelor de la 2 la N si testarea primalitatii acestora. Aceasta solutie obtine 30 de puncte si se gaseste aici. Rezolvarea de 100 de puncte se bazeaza pe folosirea Ciurului lui Erathostenes. Sursa oficiala se gaseste aici.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content