Fişierul intrare/ieşire:ciur.in, ciur.outSursăad-hoc
AutorArhiva EducationalaAdăugată defilipbFilip Cristian Buruiana filipb
Timp execuţie pe test0.1 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 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

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content