Un șir se numește vecoprim dacă pentru fiecare de la la , și sunt prime între ele.
Două numere sunt prime între ele dacă cel mai mare divizor comun al lor este .
Se dă și un șir de numere naturale nenule.
Într-o operație, poți alege un număr natural nenul și să îl inserezi oriunde în șir.
Cerință
Află numărul minim de operații ca să faci șirul să devină vecoprim.
Date de intrare
Pe prima linie a fișierului de intrare vecoprim.in
se află numărul . Pe a doua linie se află șirul .
Date de ieșire
Să se afișeze în fișierul vecoprim.out
numărul minim de operații ca să se facă șirul vecoprim.
Restricții și precizări
# | Puntaj | Restricții |
---|---|---|
1 | 20 | |
2 | 80 | Fără alte restricții |
Exemplu
vecoprim.in
6
2 4 7 3 6 1
vecoprim.out
2
Explicație
Putem să inserăm valoarea între numerele și . După, putem insera valoarea între numerele și . Șirul obținut este care este vecoprim (valorile subliniate sunt cele adăugate). Se poate demonstra că nu se poate obține un număr mai mic de operații.