| 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 Eratostene. Acest algoritm are complexitatea O(n log log n) asa cum se arata aici Sursa oficiala se gaseste aici. O sursa rapida (folosind optimizari pe biti) se gaseste aici pentru explicatii mai detaliate puteti citi acest articol
