Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | ciur.in, ciur.out | Sursă | ad-hoc |
| Autor | Arhiva Educationala | Adăugată de |  Filip Cristian Buruiana •filipb |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 7168 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Poti vedea testele pentru aceasta problema accesand atasamentele.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.in | ciur.out |
|---|---|
| 10 | 4 |
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. O surse foarte rapida (folosind optimizari pe biti) se gaseste aici.
