Проблема Макс
На світанку працьовиті бджоли готуються до польоту збирати нектар. Поблизу вулика є зачарований сад із N квітами під номерами 1, 2, N. Кількість пелюсток відома для кожної квітки.
Деякі квіти в саду можуть бути пастками. Така квітка має просте число пелюсток. Якби бджола сиділа на віночку квіткової пастки, то квітка вкрала б кількість нектару, рівну кількості пелюсток.
Інші квіти можуть бути квітами достатку. Кількість пелюсток квітки в достатку має непарну кількість дільників. Якби бджола сиділа на віночку такої квітки, то це дало б бджолі кількість нектару, що дорівнює триразовій кількості пелюсток.
Інші квіти можуть бути звичайними квітами. Якби бджола сиділа на віночку звичайної квітки, тоді квітка дав би бджолі кількість нектару, що дорівнює кількості пелюсток.
Королева вулика наказала бджолам збирати найбільшу кількість нектару, який можна зібрати з саду, інакше вони будуть вигнані з вулика.
Напишіть програму, яка зчитує натуральні цифри та кількість пелюсток кожної квітки та визначає максимальну кількість нектару, яку бджоли можуть зібрати із зачарованого саду.
Програма зчитує з клавіатури число n, а потім n натуральних чисел, що представляють кількість пелюсток кожної квітки.
Програма відобразить на екрані цифру C. .
- 1 ‰ ¤ n ‰ ¤ 100 000
- кожна квітка має максимум 10 000 пелюсток
- Нектар квітки може зібрати одна бджола.
- Максимальна кількість зібраного нектару - натуральне число, C ‰ 000 2 000 000 000
Максимальна кількість нектару отримують із квітів 1, 3, 5, 6 та 8. С = 3х25 + 3х1 + 12 + 10 + 102 = 202