|
2010-2011
|
RSA++ (100 баллов)
Исследовательский отдел министерства обороны Байтландии разработал новый сверхнадежный алгоритм шифрования. Назвать новый алгоритм решили RSA++, так как за его основу был взят знаменитый алгоритм RSA. Как известно, в основе алгоритма RSA лежит использование пары простых натуральных чисел P и Q и производного числа N = P * Q. Числа P и Q называются ключами шифрования, а число N – модулем шифрования. Простое число — это натуральное число, которое имеет ровно два различных натуральных делителя: единицу и самого себя. Принципиальным отличием нового RSA++ алгоритма от RSA алгоритма состоит в выборе ключей. Если в реализации RSA алгоритма требуется пара простых чисел P и Q, то в RSA++ алгоритме числа P и Q должны быть взаимно простыми. Два натуральных числа называются взаимно простыми, если они не имеют никаких общих делителей, кроме единицы. Для анализа надежности нового алгоритма ученые хотят узнать количество различных пар ключей P и Q, таких, что 1 < P < Q и соответствующий им модуль шифрования удовлетворяет условию: N ≤ K. Ваша задача помочь ученым в решении этого нелегкого вопроса. Входные данные Первая строка входного файла содержит одно целое число K (1 ≤ K ≤ 109). Выходные данные Выходной файл должен содержать одно целое число – количество различных пар ключей P и Q.
|