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
Se de un numar natural N.
Cerinta
Sa se determine numarul numerelor prime mai mici sau egale cu N si sa se afiseze aceste numere. In caz ca numarul de numere depaseste 1000, se vor afisa doar cele mai mari 1000 de numere.
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 numarul de numere prime mai mici sau egale cu N. A doua linie va contine numerele prime aflate. In caz ca numarul lor depaseste 1000, a doua linie va contine doar cele mai mari 1000 de numere. Numerele de pe cea de a doua linie trebuiesc afisate in ordine crescatoare.
Restrictii
- 2 ≤ N ≤ 2 000 000
Exemplu
| ciur.in | ciur.out |
|---|---|
| 10 | 4 2 3 5 7 |
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.
