Secventa EKG

O secvență de numere întregi poate fi reprezentată grafic foarte ușor, dacă adăugăm pe grafic toate punctele de coordonate (i, ai). În acest caz, i reprezintă o poziție a unui element din secvență, iar ai reprezintă elementul de pe poziția i din secvență.
De exemplu, putem reprezenta grafic secvența (1, 4, 3, 4) în felul următor:
https://ibb.co/3SBvdc7
[ https://ibb.co/3SBvdc7 - Pentru incarcare in pagina (embed) Click aici ]
[ https://ibb.co/3SBvdc7 - Pentru incarcare in pagina (embed) Click aici ]
În această problemă vei folosi o secvență de numere întregi descoperită în anul 2001 și numită Secvența EKG, datorită asemănării graficului ei cu o electrocardiogramă. Poți citi aici mai multe despre ea.
Secvența EKG e definită în felul următor:
a[1] = 1
a[2] = 2
a[n] = cel mai mic număr X care nu apare pe pozițiile anterioare în secvență, iar cmmdc(X, a[n-1]) != 1, unde cmmdc(a, b) e cel mai mare divizor comun al lui a și b
Astfel, secvența începe cu 1, 2, 4, 6, 3, 9, 12, 8, 10, 5, 15...
Cerință
Află elementul de pe poziția n din secvența EKG.
Date de intrare
Pe prima linie se află un singur număr natural, n.
Date de ieșire
Se va afișa un singur număr natural, reprezentând elementul de pe poziția n din secvența EKG.
Restricții
1 ≤ n ≤ 1000
Exemplu
Date de intrare
10
Date de ieșire
5



Cum pot sa rezolv problema cu instructiunea for ?