Рождение теоремы Ферма
В письме от 25 декабря 1640 г., великий математик Пьер де Ферма написал Марин Мерсенн, что он только что доказал, что нечетные простые числа р можно представить в виде р = a^2 + b^2, если и только если р представимо в виде p = 4c + 1. Как обычно, Ферма не включил в письмо доказательства, и, насколько нам известно, нигде его и не записал. Так сложилось, что и 100 лет спустя, никто, кроме Эйлера не доказал эту теорему. К примеру, каждое из следующих простых чисел можно представить в виде суммы двух квадратов:
5 = 2^2 + 1^2 13 = 3^2 + 2^2 17 = 4^2 + 1^2 41 = 5^2 + 4^2
В то же время простые числа 11, 19, 23 и 31 не могут быть выражены в виде суммы двух квадратов. Напишите программу для подсчета числа простых чисел, которые могут быть выражены как сумма квадратов в пределах заданного интервала.
Входные данные
Ваша программа будет опробована на одном или нескольких тестах. Каждый тестовый случай указан в отдельной строке входных данных, и определяет два целых числа L, U где L ≤ U < 1000000.
Последняя строка входного файла содержит не обрабатываемые фиктивные значения L = U = −1.
Выходные данные
Для каждого теста выведите результат, используя следующий формат:
L U x y
где L и U заданные во входных данных числа. x это общее количество простых чисел в интервале [L, U] (включительно), а y общее количество простых чисел (также из интервала [L, U]), которые могут быть выражены как сумма квадратов.