Detailed mathematical approach

Problem Summary

We must sum all integers \(n \le 10^8\) such that for every divisor \(d \mid n\), the quantity

$d+\frac{n}{d}$

is prime. A naive search would test every \(n\) and every divisor pair, which is far too slow at this bound. The local C++, Python, and Java solutions instead combine number-theoretic filters with a prime sieve so that only a much smaller family of candidates is checked in full.

Mathematical Approach

Step 1: The divisor \(d=1\) gives the first filter

If \(n\) satisfies the condition for every divisor, then in particular the choice \(d=1\) forces

$1+\frac{n}{1}=n+1$

to be prime. Therefore every valid value must be of the form

$n=p-1 \qquad (p \text{ prime}).$

This already removes almost all integers from consideration. It also explains why the implementations iterate over primes and test \(n=p-1\) rather than scanning every \(n\) directly.

Step 2: All nontrivial candidates are even, but not divisible by \(4\)

The prime \(n+1\) is larger than \(2\) unless \(n=1\). Hence \(n+1\) is odd, so every valid \(n>1\) must be even. Now suppose \(4 \mid n\). Taking \(d=2\) gives

$2+\frac{n}{2}.$

Because \(n/2\) is then even, this value is an even integer greater than \(2\), so it cannot be prime. Thus every valid \(n>1\) satisfies

$n \equiv 2 \pmod 4.$

This is exactly the fast rejection implemented by the line that discards numbers with \((n \mathbin{\&} 3) = 0\).

Step 3: The odd part must be squarefree

Assume an odd prime \(q\) satisfies \(q^2 \mid n\). Choosing \(d=q\) gives

$q+\frac{n}{q}=q\left(1+\frac{n}{q^2}\right).$

The second factor is an integer at least \(2\), so the whole expression is a multiple of \(q\) larger than \(q\), hence composite. Therefore no odd prime square can divide a valid \(n\).

Combined with the previous step, this shows that every valid \(n>1\) is squarefree and contains the prime \(2\) exactly once. The code mirrors this proof: after factoring \(n/2\), it immediately rejects the candidate if the same odd prime appears twice.

Step 4: Divisor pairs make the full verification finite and symmetric

Once a candidate survives the cheap filters, the remaining condition is still

$d+\frac{n}{d}\text{ is prime for all }d \mid n.$

Divisors come in pairs \((d,n/d)\), and both members of the pair produce the same sum. So it is enough to test only the divisors with

$d \le \frac{n}{d} \qquad \Longleftrightarrow \qquad d \le \sqrt{n}.$

For example, \(n=30\) has divisor pairs \((1,30)\), \((2,15)\), \((3,10)\), and \((5,6)\). The corresponding values are \(31,17,13,11\), all prime, so \(30\) contributes to the final sum.

Step 5: Why a prime table up to \(10^8+1\) is enough

For fixed \(n\), define \(f(d)=d+n/d\). On the interval \(1 \le d \le \sqrt{n}\), this function decreases, so the largest relevant value occurs at \(d=1\):

$d+\frac{n}{d} \le n+1.$

Since the search limit is \(n \le 10^8\), every primality query lies in the range \([2,10^8+1]\). That is why all three implementations build a prime sieve only once, up to LIMIT + 1, and then answer every primality test by constant-time table lookup.

Step 6: Matching the proof to the repository code

The three local solution files implement the same pipeline.

First, they generate a sieve of primes up to LIMIT + 1.

Second, they consider only candidates of the form n = p - 1 with \(p\) prime.

Third, the helper check_n or checkN performs the exact mathematical tests above:

$n=1 \Rightarrow \text{accept}, \qquad n \text{ odd } \Rightarrow \text{reject}, \qquad 4 \mid n \Rightarrow \text{reject}.$

Then it writes \(n=2m\) and factors the odd number \(m\) using an SPF table stored only for odd indices. If an odd prime factor repeats, the candidate is rejected because the odd part is not squarefree. Otherwise the code builds all divisors from the distinct prime factors and checks whether

$d+\frac{n}{d}$

is prime for every divisor pair.

How the Code Works

The C++ and Java versions explicitly materialize the prime list and split it into chunks for parallel processing. Each worker accumulates a partial sum over its assigned primes and the totals are added at the end. The Python version keeps the same mathematics but loops through the sieve array serially.

The SPF structure is also implementation-specific but mathematically identical. After dividing by \(2\), the remaining factor \(m\) is odd, so the code stores the smallest prime factor of an odd integer \(x\) at position \(x/2\). If the stored value is \(0\), the remainder itself is prime. This gives a compact and fast way to factor each candidate without trial division.

Complexity Analysis

The dominant preprocessing cost is building the prime sieve up to \(10^8+1\) and the odd-only SPF table up to \(10^8/2\). Both are sieve-style preprocesses with near-linear behavior, typically summarized as \(O(N \log \log N)\) time and \(O(N)\) memory for the global bound \(N=10^8\).

After preprocessing, the algorithm examines only \(\pi(N+1)\) candidates because every valid \(n\) must equal \(p-1\). Factoring a surviving candidate touches only its distinct prime factors, and divisor generation costs \(O(2^{\omega(n)})\), where \(\omega(n)\) is the number of distinct prime divisors. The squarefree restriction keeps \(\omega(n)\) small in practice, so the expensive full divisor test is applied to a very manageable set of numbers.

Footnotes and References

1. Problem page: https://projecteuler.net/problem=357
2. Prime number: Wikipedia — Prime number
3. Sieve of Eratosthenes: Wikipedia — Sieve of Eratosthenes
4. Square-free integer: Wikipedia — Square-free integer
5. Divisor function and divisor pairs: Wikipedia — Divisor