Fibo Primes
Пролетен Турнир по Информатика, 2010
Time Limit: 1s, Memory Limit: 128MiB
След като изследването на простите числа при деление на две не доведе до нищо хубаво, Ели реши да смени стратегията си. Сега тя ще дели на числа на Фибоначи.

Числата на Фибоначи са редица от естествени числа, която се дефинира рекурсивно по следния начин: F0 = 0, F1 = 1, Fi = Fi-1 + Fi-2, за i > 1. Първите няколко числа на Фибоначи са 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144...

Ели си избира едно начално естествено число N0 и прилага следните операции. В началото тя казва, че не е намерила нито едно просто число. Ако числото N0 е просто тя отбелязва, че е намерила едно просто число. След това тя си избира някое число на Фибоначи и дели N0 целочислено на него. Тъй като делението на 0 не е дефинирано, а на 1 няма голям смисъл, ще разглеждаме само деления на числа на Фибоначи, които са по-големи или равни на 2.

Например ако N0 е било 47 тя може да избере третото число на Фибоначи, което е 2, и да го раздели на него, получавайки числото N1 = 47 / 2 = 23. Двадесет и три също е просто, затова Ели си отбелязва, че е намерила две прости числа. След това тя отново избира число на Фибоначи – например отново 2 и получава N2 = 23 / 2 = 11. То също е просто, затова Ели си отбелязва, че е намерила 3 прости числа. По-нататък тя може да избере друго число на Фибоначи – например 3 – и да получи N3 = 11 / 3 = 3. То отново е просто, затова тя си отбелязва, че е намерила четвърто просто число. Оттук нататък което и число на Фибоначи да избере тя ще получи 0 или 1, никое от които не е просто и от което не могат да се получат други прости, следователно Ели приключва работата си.

Забележете обаче, че изборът на кое число на Фибоначи да дели Ели е доста важен. Например тя можеше да избере да раздели първо на 3, после на 2 и на 2, получавайки редицата {47, 15, 7, 3}, където тя би намерила 3 прости числа. Всъщност, при 47 оптималната стратегия за Ели би била да дели само и единствено на 2, получавайки {47, 23, 11, 5, 2} – общо 5 прости числа. Това, обаче, не винаги е вярно. При числото 65 би било най-изгодно за нея да дели на 5, и после отново на 5 (или пък на 5, после на 2 и отново на 2) получавайки съответно редиците {65, 13, 2} или {65, 13, 6, 3}, всяка от които съдържа по 2 прости числа.

По дадено начално число N0 да определите колко най-много прости числа може да намери Ели ако ползва оптимални деления.
Вход
На единствен ред на стандартния вход ще бъде зададено цялото числото N0, с което започва Ели.
Изход
На стандартния изход изведете едно единствено цяло число – колко най-много прости числа може да намери Ели, спазвайки описания алгоритъм.
Ограничения
  • 1 ≤ N0 ≤ 1012
Примерен Вход Примерен Изход
475
652
4213374210
Една от възможните последователности за числото 42133742 е {42133742, 14044580, 4681526, 2340763, 292595, 146297, 18287, 6095, 3047, 1523, 761, 95, 47, 23, 11, 5, 2} от които прости са {2340763, 146297, 18287, 1523, 761, 47, 23, 11, 5, 2}.
Мрън!