- All Contests
- ProjectEuler+
- Project Euler #153: Investigating Gaussian Integers

# Project Euler #153: Investigating Gaussian Integers

# Project Euler #153: Investigating Gaussian Integers

_{This problem is a programming version of Problem 153 from projecteuler.net}

As we all know the equation has no solutions for real .

If we however introduce the imaginary number this equation has two solutions: and .

If we go a step further the equation has two complex solutions: and .

and are called each others' complex conjugate.

Numbers of the form are called complex numbers.

In general and are each other's complex conjugate.

A Gaussian Integer is a complex number such that both and are integers.

The regular integers are also Gaussian integers (with ).

To distinguish them from Gaussian integers with we call such integers "rational integers."

A Gaussian integer is called a divisor of a rational integer if the result is also a Gaussian integer.

If for example we divide by we can simplify in the following manner:

Multiply numerator and denominator by the complex conjugate of : .
The result is

So is a divisor of .

Note that is not a divisor of because .

Note also that if the Gaussian Integer is a divisor of a rational integer , then its complex conjugate is also a divisor of .

In fact, has six divisors such that the real part is positive: .

The following is a table of all of the divisors for the first five positive rational integers:

For divisors with positive real parts, then, we have .

For , .

What is for ?

**Input Format**

First and only line of each test file contains a single integer .

**Constraints**

**Output Format**

Output the only integer - the answer to the problem.

**Sample Input**

```
5
```

**Sample Output**

```
35
```