Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | prim.in, prim.out | Sursă | info-arena 1.0 |
| Autor | Dan Popovici | Adăugată de | |
| Timp execuţie pe test | 0.075 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate |   1/5 |
Vezi solutiile trimise | Statistici
Numere Prime
Gheorghe a invatat la scoala despre numere prime. A invatat ca un numar este prim, daca se divide doar cu 1 si cu el insusi($1$ nu este considerat numar prim). A aflat ca exista algoritimi foarte eficienti care pot determina daca un numar este prim sau nu, in timp chiar sub polinomial. Din pacate acesti algoritmi sunt foarte complicati, si Gheorghe s-a gandit la o aproximare. Idea lui este sa consideri un numar prim daca nu se divide la primele K numere prime.
Cerinta
Demonstreaza ca ideea lui Ghoerghe este doar o aproximare. Dandu-se un numar K, afla cel mai mic numar N care nu este divisibil cu primele K numele prime, dar nu este prim.
Date de Intrare
Pe prima linie din fisierul prim.in se va afla numarul K.
Date de Iesire
Pe prima linie a fisierului prim.out se va gasi numarul N cautat.
Restrictii
- 1 ≤ K ≤ 100.000
Exemplu
| prim.in | prim.out | Explicatii |
|---|---|---|
| 1 | 9 | 9 nu este divizibil cu 2 si nu este nici prim |
| 3 | 49 | primele 3 numere prime sunt 2,3,5. Numerele care nu sunt divisibile cu 2,3 sau 5 sunt : 7, 11, 13, 17, 19, 23, 31, 37, 41, 47, 49 ,... 49 este cel mai mic numar care nu este prim. |
