Ограничение по времени: 2.000 секунд
Ограничение по памяти: 500.000 мегабайт
В этой задаче нет истории.
Вам дано n натуральных чисел a1, a2, ... , an. Нужно найти размер наибольшего подмножества этих чисел, что НОД чисел в подмножестве строго больше единицы. НОД множества чисел - это наибольшее натуральное число, делящее все числа из множества.
В первой строке дано одно целое число n (1 ⩽ n ⩽ 1000) - количество натуральных чисел.
Во второй строке даны n натуральных чисел ai (2 ⩽ ai ⩽ 1018).
Выведите одно целое число - размер наибольшего подмножества данных чисел, что НОД чисел в этом подмножестве строго больше единицы.
| input | output |
|---|---|
46 15 10 42 |
3 |
32 2 2 |
3 |
135 |
1 |
В первом тесте можно выбрать множество {6, 15, 42}, НОД чисел в этом множестве равен 3.