Fişierul intrare/ieşire:prim.in, prim.outSursăinfo-arena 1.0
AutorDan PopoviciAdăugată de
Timp execuţie pe test0.15 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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 Gheorghe este doar o aproximare. Dandu-se un numar K, afla cel mai mic numar N mai mare decat 1 care nu este divizibil cu primele K numere 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

Exemple

prim.inprim.out
1
9

Explicatii

9 nu este divizibil cu 2 si nu este nici prim.

prim.inprim.out
3
49

Explicatii

Primele 3 numere prime sunt 2, 3, 5. Numerele care nu sunt divizibile 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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content