ciur

Ciur

== include(page="template/taskheader" task_id="ciur") ==

Poveste si cerinta...

Spunem ca un numar natural $x$ este prim daca si numai daca $x > 1$ si singurii sai divizori sunt $1$ si $x$.
 
h2. Cerinta
 
Dandu-se un numar natural $N$, sa se determine numarul numerelor prime mai mici sau egale cu $N$.

h2. Date de intrare

Fisierul de intrare $ciur.in$ ...

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

h2. Date de iesire

In fisierul de iesire $ciur.out$ ...

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

h2. Restrictii

* $... ≤ ... ≤ ...$

* $2 ≤ N ≤ 2 000 000$

h2. Exemplu
table(example). |_. ciur.in |_. ciur.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

|10|4|
 
h2. Indicatii de rezolvare
 
bq. Sift the Two's and sift the Three's, The Sieve of Eratosthenes. When the multiples sublime, The numbers that remain are Prime.  :)

h3. Explicatie

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':job_detail/153307?action=view-source. Rezolvarea de 100 de puncte se bazeaza pe folosirea 'Ciurului lui Eratostene':http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes. Acest algoritm are complexitatea $O(n log log n)$ asa cum se arata 'aici':http://infoarena.ro/blog/intrebare-scurta Sursa oficiala se gaseste 'aici':job_detail/153303?action=view-source. O sursa rapida (folosind optimizari pe biti) se gaseste 'aici':job_detail/153333?action=view-source pentru explicatii mai detaliate puteti citi acest 'articol':http://infoarena.ro/ciurul-lui-eratostene

...

== include(page="template/taskfooter" task_id="ciur") ==

2775