Prime Containers
TopCoder MRM 471
Time Limit: 0.1s, Memory Limit: 64MiB
Ели много харесва div 2 задачи! И под това тя разбира задачи, в които се дели на две. Тя забелязва, че някои числа съдържат в себе си прости числа! Едно число съдържа прости ако самото то е просто, ако разделено на две (закръглено надолу) е просто, разделено на четири (отново закръглено надолу) е просто и, като цяло ако числото разделено на 2k (закръглено надолу) е просто.

Ели счита всички естествени числа за "контейнери на прости числа". Размерът на даден контейнер (дадено число N) тя дефинира като броят прости числа, които се съдържат в N. Например 7 е с размер 2, тъй като 7 и 7/2 = 3 са прости; 47 е с размер 5, тъй като 47, 23, 11, 5 и 2 са прости; 959 е с размер 6 и съдържа простите {479, 239, 59, 29, 7, 3}.

Помогнете на Елеонора като по дадено число N върнете броя прости числа, които то съдържа.
Вход
На единствен ред на стандартния вход ще бъде зададено цялото число N.
Изход
На стандартния изход изведете едно цяло число – броя прости числа, съдържани в N.
Ограничения
  • 1 ≤ N ≤ 2,000,000,000
Примерен Вход Примерен Изход
102
422
475
9596
426844798
В първия пример, числото 10 съдържа простите 5 и 2. Във втория пример, макар и отговор на Живота, Вселената и Всичко Останало, 42 се оказва, че не е много голям контейнер.
Мрън!