vecoprim

Time limit: 0.3s Memory limit: 64MB Input: vecoprim.in Output: vecoprim.out

Un șir x1,x2,xNx_1, x_2, \dots x_N se numește vecoprim dacă pentru fiecare ii de la 11 la N1N − 1, xix_i și xi+1x_{i+1} sunt prime între ele.
Două numere sunt prime între ele dacă cel mai mare divizor comun al lor este 11.

Se dă NN și un șir a1,a2,aNa_1, a_2, \dots a_N de numere naturale nenule.
Într-o operație, poți alege un număr natural nenul xx și să îl inserezi oriunde în șir.

Cerință

Află numărul minim de operații ca să faci șirul aa să devină vecoprim.

Date de intrare

Pe prima linie a fișierului de intrare vecoprim.in se află numărul NN. Pe a doua linie se află șirul a1,a2,aNa_1, a_2 \dots, a_N.

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

  • 2N100 0002 \leq N \leq 100 \ 000
  • 1ai1091 \leq a_i \leq 10^9
# Puntaj Restricții
1 20 N=2N = 2
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 33 între numerele 22 și 44. După, putem insera valoarea 55 între numerele 33 și 66. Șirul obținut este 2,3,4,7,3,5,6,12,\underline{3},4,7,3,\underline{5},6,1 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.

Log in or sign up to be able to send submissions!