Coprimes - Easy
TopCoder SRM 577
Time Limit: 0.1s, Memory Limit: 64MiB
Ели има множество от различни положителни цели числа A1, A2, ..., AN. Тя иска да допълни множеството с няколко (потенциално нула) нови положителни цели числа, по такъв начин, че ако сортира множеството, никои две съседни числа да нямат общ делител, по-голям от едно.

Сега Ели се чуди колко най-малко допълнителни числа трябва да добави, за да постигне това?
Вход
На първия ред на стандартния вход ще бъде зададено едно цяло число N – броя числа, които Ели има в началото. На следващия ред ще бъдат зададени N цели положителни числа A1 A2 ... AN – самите стойности на числата.
Изход
На стандартния изход изведете едно цяло число – минималния брой допълнителни числа, които момичето трябва добави в множеството.
Ограничения
  • 1 ≤ N ≤ 50
  • 1 ≤ Ai ≤ 100,000
Примерен Вход Примерен Изход
4 2200 42 2184 17 3
44 55780 44918 55653 4762 41536 40083 79260 7374 24124 91858 7856 12999 64025 12706 19770 71495 32817 79309 53779 8421 97984 34586 893 64549 77792 12143 52732 94416 54207 51811 80845 67079 14829 25350 22976 23932 62273 58871 82358 13283 33667 64263 1337 42666 15
В първия пример едно възможно решение е да добави числата {43, 2195, 2199}. Така сортираното множество ще бъде (17, 42, 43, 2184, 2195, 2199, 2200). Можете да видите, че никои две съседни числа в него нямат общ делител, по-голям от едно.
Мрън!