==Include(page="template/taskheader" task_id="prim")==

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.

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.

h2. 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.

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.

h2. Date de Intrare

h2. Date de intrare

Pe prima linie din fisierul $prim.in$ se va afla numarul $K$.

h2. Date de Iesire

h2. Date de iesire

Pe prima linie a fisierului $prim.out$ se va gasi numarul $N$ cautat.

* $1 ≤ K ≤ 100.000$

h2. Exemplu

h2. Exemple

table(example). |_. prim.in |_. prim.out |_. Explicatii |

table(example). |_. prim.in |_. prim.out |

| 1

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

| 9 |
 
h3. Explicatii
 
$9$ nu este divizibil cu $2$ si nu este nici prim.
 
table(example). |_. prim.in |_. prim.out |

| 3
| 49 |
h3. Explicatii

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.

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.
 
==Include(page="template/taskfooter" task_id="prim")==
 

==Include(page="template/taskfooter" task_id="prim")==

49