Fermat's Christmas Theorem

Time limit1sMemory limit128 MB

Summary

For each query interval, count the primes in it and how many of those satisfy the sum-of-two-squares criterion.

Level: Medium4 of 10
Topics: Number theory, Math
Solved: No attempts yet

Problem

On December 25, 1640, the great mathematician Pierre de Fermat sent Marin Mersenne a letter containing the following claim.

I have just proved that an odd prime $p$ can be written as $p = a^2 + b^2$ if and only if $p$ can be written as $p = 4c + 1$ .

The letter contained no proof; Euler proved it 100 years later. Indeed, $5,\ 13,\ 17,\ 41$ can each be written as a sum of two squares.

$5 = 2^2 + 1^2 \qquad 13 = 3^2 + 2^2 \qquad 17 = 4^2 + 1^2 \qquad 41 = 5^2 + 4^2$

By contrast, $11,\ 19,\ 23,\ 31$ cannot be written as a sum of two squares.

Here the two squares are squares of non-negative integers, and the prime $2 = 1^2 + 1^2$ also counts as a sum of two squares.

Given an interval $[L, U]$ , write a program that counts how many primes in the interval can be written as a sum of two squares.

Input

The input consists of several test cases. Each test case is a single line containing two integers $L$ and $U$ separated by a space. ( $-1{,}000{,}000 < L \le U < 1{,}000{,}000$ )

In the last line, $L$ and $U$ are both equal to $-1$ ; this line is not processed.

Output

For each test case, print four integers $L$ , $U$ , $x$ , $y$ on one line, separated by spaces. $L$ and $U$ are the given input values, $x$ is the number of primes in the interval $[L, U]$ , and $y$ is the number of those primes that can be written as a sum of two squares.

Examples3

Example 1

Input

Expected output

10 20 4 2
11 19 4 2
100 1000 143 69

Example 2
Input
```
2 2
-1 -1
```
Expected output
```
2 2 1 1
```
Example 3
Input
```
3 3
-1 -1
```
Expected output
```
3 3 1 0
```