Простой наибольший общий делитель
(Время: 0,25 сек. Память: 32 Мб Сложность: 92%)
Для заданных N и M вычислите количество таких пар натуральных чисел i и j (1 ≤ i ≤ N, 1 ≤ j ≤ M), что НОД(i, j) является простым числом (НОД – наибольший общий делитель).
Простым числом называется натуральное число (большее 1), которое делится нацело только на 1 и на само себя.
Входные данные
Входной файл INPUT.TXT содержит два натуральных числа N и M (1 ≤ N, M ≤ 3141592653).
Выходные данные
В выходной файл OUTPUT.TXT выведите ответ на задачу.
Примеры
| № | INPUT.TXT | OUTPUT.TXT |
|---|
| 1 | 3 3 | 2 |
| 2 | 26 43 | 311 |
Пояснение к первому примеру
Здесь простой НОД мы получаем только в двух случаях: для НОД(2, 2) = 2 и НОД(3, 3) = 3. В остальных случаях НОД(i, j) = 1.
Автор задачи
Владимир Игоревич Лукьянчиков
Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!
| 
