Rezolvare PBinfo #3278

Spunem că un număr natural este aproape prim dacă el poate fi scris ca produs de două numere prime. De exemplu 6 și 25 sunt aproape prime pentru că 6 = 2 * 3, iar 25 = 5 * 5. Considerăm șirul crescător al numerelor naturale aproape prime: 4, 6, 9, 10, 14, 15, 21, … Acestora li se asociază câte un număr de ordine, numerotarea începând cu 1. Deci 4 este primul număr aproape prim, 6 este al doilea număr, 9 este al treilea etc.

Cerința

Dat un număr natural N, să se determine al N-lea număr aproape prim.

Date de intrare

Programul citește de la tastatură numărul N.

Date de ieșire

Programul va afișa pe ecran un singur număr natural, reprezentând al N-lea număr aproape prim.

Restricții și precizări

• 1 ≤ N ≤ 23.378

Exemplul 1:

Intrare

4

Ieșire

10

Exemplul 2:

Intrare

300

Ieșire

1003