Problem 357: Prime Generating Integers

Project Euler Problem 357 Solution

EulerSolve provides an optimized solution for Project Euler Problem 357, Prime Generating Integers, with C++, Python, Java, and a step-by-step mathematical explanation.

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....

Detailed mathematical approach

Problem Summary

Call a positive integer $n$ prime generating when $d+n/d$ is prime for every divisor $d$ of $n$. The statement illustrates this with $n=30$, whose divisors $1,2,3,5,6,10,15,30$ all pass, and asks for the sum of all prime generating $n\le100\,000\,000$. ^[1]

The whole solution in one sentence: the divisor $d=1$ forces $n+1$ to be prime and the divisor $d=q$ forbids a prime square $q^2$, so one sieve up to $10^8+1$ supplies the few candidates $n=p-1$ and settles every later primality question by a table lookup.

Mathematical Approach

1. The condition on one number

The eight divisors of $30$ form four pairs with product $30$, each giving one value:

$$\begin{aligned}1+30&=31, & 2+15&=17,\\ 3+10&=13, & 5+6&=11.\end{aligned}$$

All four are prime, so $30$ qualifies; the divisors $6,10,15,30$ only repeat these sums in reverse order. Three neighbours fail differently: $n=34$ at the very first test, $1+34=35=5\cdot7$; $n=18$ only at the third, $3+6=9$; $n=46$ at the second, $2+23=25$, after the prime $47$.

2. Divisors come in pairs

If $d$ divides $n$ then so does $n/d$, and replacing $d$ by $n/d$ only swaps the two summands, so both give the same value: it is enough to test the divisors with $d\le\sqrt n$. Call an integer squarefree when no prime occurs more than once in its factorisation. ^[2] For $30=2\cdot3\cdot5$, choosing which of the three primes to include produces each divisor exactly once, $1$ when none is chosen, so a squarefree number with $\omega$ distinct primes has exactly $2^{\omega}$ divisors. For squarefree $n\gt1$ none of them equals its partner, since $d=n/d$ would make $n=d^2$ a square, so they form $2^{\omega-1}$ pairs.

3. The first filter: $n+1$ must be prime

Taking $d=1$ gives $1+n/1=n+1$, so $n+1$ is prime for every prime generating $n$. That alone shrinks the search from $10^8$ integers to the $5761455$ values $n=p-1$ with $p\le10^8+1$ prime — a factor of about $17$, free of charge, since those primes must be sieved anyway.

4. Even, but never a multiple of four

The integer $1$ has the single divisor $1$, and $1+1=2$ is prime, so $1$ qualifies. For $n\gt1$ the prime $n+1$ is at least $3$ and hence odd, so $n$ is even. If $4$ divided $n$, the divisor $d=2$ would have $n/2$ even, making $2+n/2$ an even number of at least $4$, never prime. So $n\equiv2\pmod4$ for every prime generating $n\gt1$, equivalently $n+1\equiv3\pmod4$. Exactly $2880950$ primes up to $10^8+1$ are $3$ modulo $4$; with $p=2$, giving $n=1$, that leaves $2880951$ candidates — as the sequence entry also notes. ^[3]

5. The number must be squarefree

Let $q$ be a prime with $q^2\mid n$. Then $q$ divides $n$ and

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

whose second factor is an integer of at least $2$. The value is a multiple of $q$ larger than $q$, hence composite. So prime generating integers are squarefree, and with Section 4 every one above $1$ has the shape $n=2m$ with $m$ odd and squarefree. The smallest candidate this removes is $18$: here $19$ is prime and $18\equiv2\pmod4$, but $18=2\cdot3^2$ and $3+6=9$.

That shape also explains why the condition is satisfiable at all: writing $d=2^{a}d'$ with $d'$ odd gives $a\in\{0,1\}$, so exactly one of $d$ and $n/d$ is even and every pair sum is odd.

6. The complete test

Claim. A positive integer $n$ is prime generating exactly when $n=1$, or $n\equiv2\pmod4$, the odd half $n/2$ is squarefree, and $d+n/d$ is prime for every divisor $d$ of $n$ with $d\le\sqrt n$.

Necessity is Sections 3 to 5 plus the restriction to $d\le\sqrt n$. For sufficiency, $n\equiv2\pmod4$ with $n/2$ squarefree makes $n$ squarefree, so by Section 2 each divisor above $\sqrt n$ repeats the sum of a tested one. That $n+1$ be prime is no extra demand: it is the case $d=1$.

7. One sieve answers every question

For any divisor $d$ the numbers $d-1$ and $n/d-1$ are non-negative, so

$$\begin{aligned}(d-1)\left(\frac nd-1\right)&\ge0,\\[2pt] d+\frac nd&\le n+1,\end{aligned}$$

with equality exactly at $d=1$ and $d=n$. Every primality question below the bound $10^8$ therefore concerns an integer of at most $10^8+1$, so one sieve of Eratosthenes to that value ^[4] answers all of them and lists the candidate primes too. The bound is reached at $d=1$, though $10^8+1=17\cdot5882353$ is itself composite, so the last prime in the table lies below it.

8. Worked example: everything up to $100$

Of the $26$ primes $p\le101$, keeping $p=2$ and those with $p\equiv3\pmod4$ leaves $14$ candidates:

$$1,2,6,10,18,22,30,42,46,58,66,70,78,82.$$

Squarefreeness removes $18$ alone; the divisor test removes $46$, failing at $2+23=25$, and $66=2\cdot3\cdot11$, which passes $1+66=67$ and $6+11=17$ but fails at $2+33=35$ — every pair really must be examined. The eleven survivors $1,2,6,10,22,30,42,58,70,78,82$ sum to $401$; up to $1000$ there are $28$ with sum $8427$, up to $10^4$ there are $80$ with sum $262615$, and up to $10^6$ there are $1289$ with sum $524402305$.

9. The numbers with exactly two prime factors

The case $n=2q$ with $q$ an odd prime settles by hand: the divisors are $1,2,q,2q$ and the pair sums are $2q+1$ and $q+2$. So $2q$ is prime generating exactly when $q$, $q+2$ and $2q+1$ are all prime — $q$ is the smaller member of a twin prime pair and also a Sophie Germain prime. ^[5] The smallest such $q$ are $3,5,11,29,41,179,191,239,281$, ^[6] giving $6,10,22,58,82,358,382,478,562$. Fully $30301$ of the $39627$ prime generating integers up to $10^8$ have this shape, so the problem is dominated by a pattern whose infinitude is a famous open question — as is that of the prime generating integers. ^[3]

10. How many candidates survive

At the bound $10^8$ the filters leave in turn $5761455$ integers with $n+1$ prime, $2880951$ that are $1$ or $2$ modulo $4$, and $2154865$ that are $1$ or have a squarefree odd half; finally $39627$ qualify. As $n=1$ is accepted at once, $2154864$ candidates build a divisor list and their pair tests make $4712266$ lookups, about $2.2$ each. The lookup at $d=1$ can never fail, $n+1$ being known prime already, and $1819940$ of the $2115238$ rejections happen at the next one, $d=2$.

Besides $1$ and $2$, $30301$ survivors have two distinct primes, $9009$ three, $312$ four, and exactly three have five:

$$\begin{aligned}186162&=2\cdot3\cdot19\cdot23\cdot71,\\ 899970&=2\cdot3\cdot5\cdot131\cdot229,\\ 3047410&=2\cdot5\cdot19\cdot43\cdot373.\end{aligned}$$

The first has $32$ divisors, so sixteen sums are prime at once, from $426+437=863$ to $1+186162=186163$. The counts for $n\le10^k$, $k=1,\dots,8$, are $4,11,28,80,277,1289,6625,39627$, and the largest inside the bound is $99996982=2\cdot49998491$, with $49998493$ and $99996983$ prime as Section 9 demands.

How the Code Works

sieve_primes builds the flag array up to limit + 1: it clears $0$, $1$ and the even indices from $4$ on, then for each odd $p$ still marked prime with $p^2$ inside the bound it clears $p^2,p^2+2p,p^2+4p,\dots$ — the standard sieve, since smaller multiples of $p$ carry a smaller factor. ^[4] build_spf_odd, whose own bound is $10^8/2$, then stores the smallest prime factor of every odd composite up to it. Section 5 leaves only the odd half $m=n/2$ to factor, so the entry for an odd $x$ sits at index $x/2$ in integer division and $25000001$ slots suffice. Going through the odd primes in order, the loop writes $p$ at index $j/2$ for $j=p^2,p^2+2p,\dots$ only where the slot is still $0$, so the smallest factor wins. Primes stay unmarked, so for odd $x\gt1$ a slot left at $0$ means $x$ is prime; the slot of $1$ is $0$ too, but the factoring loop runs only while $m\gt1$.

check_n is Section 6 in code order: it accepts $n=1$, rejects odd $n$ with n & 1 and multiples of four with (n & 3) == 0, then factors $m=n/2$ by reading spf_odd[m / 2] repeatedly, treating $0$ as "$m$ is prime", appending the factor and dividing. The following if (m % p == 0) return false catches $q^2\mid n$ at the first repeat, applying Section 5 before any divisor list exists. The divisors are then built by doubling: each distinct prime multiplies the current list, starting from $\{1\}$, and the products are appended, giving all $2^{\omega}$ divisors. The last loop sets $q=n/d$, skips $d\gt q$ by Section 2 and asks the sieve about $d+q$, an index Section 7 keeps inside the table.

The three files drive this differently. C++ and Java use the helpers above — Java spells them sievePrimes, buildSpfOdd and checkN — collect the primes into a list and accumulate over blocks of it; C++ also reuses one factor and one divisor vector across candidates, where Python and Java allocate fresh lists. Python builds both tables inside solve itself, scans every index from $2$ to LIMIT + 1, skips the clear flags and calls its nested check_n with one running total. The guard if (n > limit) continue can never fire, since a prime of at most limit + 1 leaves $n$ inside the bound.

The two tables cost very different amounts. The C++ vector<bool> packs a bit per entry, $12.5$ MB for its $10^8+2$ flags, where the Java boolean[] and the Python bytearray spend a byte each, about $100$ MB. Java's int[] factor table matches the C++ vector<uint32_t>, but Python's spf_odd holds $50000001$ references when no index above $25000000$ is used, twice what it needs; Java also boxes each prime and divisor as an Integer or Long. The accumulator needs no delicate reasoning: the sum of all integers up to $N=10^8$ is $N(N+1)/2$, far below $2^{63}$, so C++'s uint64_t and Java's long are safe in advance. No file has a self-test, but the C++ takes the search limit as its first argument, easing small-scale checks.

Complexity and Verification

The two sieves take $O(N\log\log N)$ time and $O(N)$ memory for $N=10^8$. ^[4] Enumerating the candidates costs $O(N)$ too, since C++ and Java scan the odd flags for their prime list while Python scans every index. The work on one candidate is set by its number of distinct primes, at most eight here because the first nine primes multiply to $223092870\gt10^8$: at most seven factor-table reads, $255$ multiplications for its $2^{\omega}\le256$ divisors and $128$ lookups. That holds for every candidate reaching the divisor stage, not only the survivors — $13123110=2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot19\cdot23$ gets all $256$ of its divisors built before rejection at $d=6$, and $155$ candidates have eight prime factors. On average it stays mild, $38001118$ divisors for the $2154864$ candidates of Section 10, and $O(N\log N)$ is a safe coarse bound for the whole run, since all integers up to $N$ have $\sum_{d\le N}\lfloor N/d\rfloor\le N(1+\ln N)$ divisors together.

One machine's figures, so dependent on its hardware, compiler and runtime settings: C++ $0.39$ s and $139$ MB, close to the $12.5+100+23$ MB of its arrays; Java $0.55$ s, out of memory at a $350$ MB heap and $456$ MB peak when given $400$ MB; Python $9.45$ s and $614$ MB. Array payloads only bound a process from below.

Three checks were run for this article. A brute force over every $n\le N$ that finds divisors by trial division and tests each sum with Miller–Rabin on the bases $2,3,5,7$, deterministic far above this range, ^[7] uses no theory from above and matches the published C++ at $N=100,1000,10^4,10^5,10^6$: counts $11,28,80,277,1289$ and sums $401$, $8427$, $262615$, $9157937$, $524402305$. A second program drops $n=p-1$ and walks all $n\equiv2\pmod4$, again with Miller–Rabin; it agrees at $10^7$, where $6625$ numbers sum to $27814470277$, and at $10^8$, finding the same $39627$ numbers and total. The three published programs, run at their own bound, printed identical output byte for byte. None of these checks is packaged in them. ^[8]

Footnotes and References

The references supply the background facts; the filters, the claim of Section 6, the bound $d+n/d\le n+1$ and the two-factor characterisation are proved above.

Project Euler 357 — Prime Generating Integers. The official statement lists the divisors of 30, notes that d + 30/d is prime for each, and asks for the sum of all positive integers n up to 100 000 000 with d + n/d prime for every divisor d.
Wikipedia — Square-free integer: divisible by no square but 1, equivalently no prime with exponent above one, of density 6/π² ≈ 0.6079. The uniqueness of a prime factorisation is the fundamental theorem of arithmetic, relied on in Sections 2 and 5.
OEIS A080715 — numbers k such that a + b is prime whenever ab = k. The entry begins 1, 2, 6, 10, 22, 30, 42, 58, 70, 78, 82, …, says that apart from 1 every member is even and square-free, that n + 1 is a prime equal to 2 or 3 modulo 4, and that whether the sequence is infinite is open.
Wikipedia — Sieve of Eratosthenes. Crossing off the multiples of p may begin at p² and stop once p² exceeds n; the plain array version is O(n log log n) time and O(n) memory.
Wikipedia — Twin prime defines a twin prime as a prime 2 away from another and calls their infinitude unknown; Wikipedia — Sophie Germain prime defines such a p by 2p + 1 being prime and reports the same open status. Section 9 needs both.
OEIS A045536 — primes p such that p + 2 and 2p + 1 are also prime. Its terms 3, 5, 11, 29, 41, 179, 191, 239, 281, 419, … are exactly the odd primes q for which 2q is prime generating, by Section 9.
Wikipedia — Miller–Rabin primality test. Its section on small sets of bases states that a = 2, 3, 5, 7 decides primality for every n below 3 215 031 751, which covers everything the cross-checks test.
C++ — Euler357.cpp. The linked immutable revision contains sieve_primes, build_spf_odd, check_n and solve as described; it is the implementation record for this article, the comparisons above being extra validation.

Problem 357 source code

C++

#include <algorithm>
#include <cmath>
#include <cstdint>
#include <cstdlib>
#include <iostream>
#include <thread>
#include <vector>

using namespace std;

namespace {

constexpr int kLimit = 100000000;

vector<bool> sieve_primes(int n) {
    vector<bool> is_prime(n + 1, true);
    if (n >= 0) is_prime[0] = false;
    if (n >= 1) is_prime[1] = false;
    for (int i = 4; i <= n; i += 2) {
        is_prime[i] = false;
    }
    for (int p = 3; 1LL * p * p <= n; p += 2) {
        if (!is_prime[p]) continue;
        for (long long j = 1LL * p * p; j <= n; j += 2LL * p) {
            is_prime[j] = false;
        }
    }
    return is_prime;
}

vector<uint32_t> build_spf_odd(int limit) {
    vector<uint32_t> spf(limit / 2 + 1, 0);
    int root = static_cast<int>(sqrt(limit));
    for (int p = 3; p <= root; p += 2) {
        if (spf[p / 2] != 0) continue;
        long long step = 2LL * p;
        long long start = 1LL * p * p;
        for (long long j = start; j <= limit; j += step) {
            if (spf[j / 2] == 0) spf[j / 2] = static_cast<uint32_t>(p);
        }
    }
    return spf;
}

bool check_n(int n,
             const vector<bool>& is_prime,
             const vector<uint32_t>& spf_odd,
             vector<int>& factors,
             vector<uint64_t>& divisors) {
    if (n == 1) return true;
    if (n & 1) return false;
    if ((n & 3) == 0) return false;

    int m = n / 2;
    factors.clear();
    factors.push_back(2);
    while (m > 1) {
        int p = spf_odd[m / 2];
        if (p == 0) p = m;
        factors.push_back(p);
        m /= p;
        if (m % p == 0) return false;
    }

    divisors.clear();
    divisors.push_back(1);
    for (int p : factors) {
        size_t size = divisors.size();
        for (size_t i = 0; i < size; ++i) {
            divisors.push_back(divisors[i] * static_cast<uint64_t>(p));
        }
    }

    uint64_t nn = static_cast<uint64_t>(n);
    for (uint64_t d : divisors) {
        uint64_t q = nn / d;
        if (d > q) continue;
        if (!is_prime[d + q]) return false;
    }
    return true;
}

uint64_t solve(int limit, int threads) {
    if (limit < 1) return 0;

    int max_prime = limit + 1;
    vector<bool> is_prime = sieve_primes(max_prime);

    vector<int> primes;
    primes.reserve(max_prime / 10);
    if (max_prime >= 2 && is_prime[2]) primes.push_back(2);
    for (int i = 3; i <= max_prime; i += 2) {
        if (is_prime[i]) primes.push_back(i);
    }

    int half = limit / 2;
    vector<uint32_t> spf_odd = build_spf_odd(half);

    if (threads < 1) threads = 1;
    if (threads > static_cast<int>(primes.size())) {
        threads = static_cast<int>(primes.size());
    }

    vector<uint64_t> partial(threads, 0);
    vector<thread> pool;
    pool.reserve(threads);
    size_t chunk = (primes.size() + threads - 1) / threads;

    for (int t = 0; t < threads; ++t) {
        size_t start = static_cast<size_t>(t) * chunk;
        size_t end = min(primes.size(), start + chunk);
        pool.emplace_back([&, start, end, t]() {
            vector<int> factors;
            factors.reserve(8);
            vector<uint64_t> divisors;
            divisors.reserve(256);
            uint64_t local = 0;
            for (size_t i = start; i < end; ++i) {
                int n = primes[i] - 1;
                if (n > limit) continue;
                if (check_n(n, is_prime, spf_odd, factors, divisors)) {
                    local += static_cast<uint64_t>(n);
                }
            }
            partial[t] = local;
        });
    }

    for (auto& th : pool) th.join();

    uint64_t total = 0;
    for (uint64_t s : partial) total += s;
    return total;
}

}  // namespace

int main(int argc, char** argv) {
    int limit = kLimit;
    int threads = static_cast<int>(thread::hardware_concurrency());
    if (threads <= 0) threads = 1;
    if (argc > 1) limit = max(1, atoi(argv[1]));
    if (argc > 2) threads = max(1, atoi(argv[2]));

    uint64_t answer = solve(limit, threads);
    cout << answer << endl;
    return 0;
}

Python

import math

def solve():
    LIMIT = 100_000_000

    # Sieve primes up to LIMIT + 1
    max_p = LIMIT + 1
    is_prime = bytearray(b'\x01' * (max_p + 1))
    is_prime[0] = 0
    is_prime[1] = 0
    for i in range(4, max_p + 1, 2):
        is_prime[i] = 0
    p = 3
    while p * p <= max_p:
        if is_prime[p]:
            for j in range(p*p, max_p + 1, 2*p):
                is_prime[j] = 0
        p += 2

    # Build SPF for odd numbers up to LIMIT/2
    half = LIMIT // 2
    spf_odd = [0] * (half + 1)
    root = math.isqrt(half)
    p = 3
    while p <= root:
        if spf_odd[p // 2] == 0:
            for j in range(p*p, half + 1, 2*p):
                if spf_odd[j // 2] == 0:
                    spf_odd[j // 2] = p
        p += 2

    def check_n(n):
        if n == 1:
            return True
        if n & 1:
            return False
        if n & 3 == 0:
            return False
        m = n // 2
        factors = [2]
        while m > 1:
            p = spf_odd[m // 2]
            if p == 0:
                p = m
            factors.append(p)
            m //= p
            if m % p == 0:
                return False

        # Generate all divisors
        divisors = [1]
        for p in factors:
            size = len(divisors)
            for i in range(size):
                divisors.append(divisors[i] * p)

        for d in divisors:
            q = n // d
            if d > q:
                continue
            if not is_prime[d + q]:
                return False
        return True

    total = 0
    # Check n = p - 1 for each prime p
    for p in range(2, max_p + 1):
        if not is_prime[p]:
            continue
        n = p - 1
        if n > LIMIT:
            continue
        if check_n(n):
            total += n

    return str(total)

if __name__ == '__main__':
    print(solve())

Java

import java.util.*;
import java.util.concurrent.*;

public class Euler357 {
    static boolean[] sievePrimes(int n) {
        boolean[] isPrime = new boolean[n + 1];
        Arrays.fill(isPrime, true);
        if (n >= 0)
            isPrime[0] = false;
        if (n >= 1)
            isPrime[1] = false;
        for (int i = 4; i <= n; i += 2)
            isPrime[i] = false;
        for (int p = 3; (long) p * p <= n; p += 2) {
            if (!isPrime[p])
                continue;
            for (long j = (long) p * p; j <= n; j += 2L * p) {
                isPrime[(int) j] = false;
            }
        }
        return isPrime;
    }

    static int[] buildSpfOdd(int limit) {
        int[] spf = new int[limit / 2 + 1];
        int root = (int) Math.sqrt(limit);
        for (int p = 3; p <= root; p += 2) {
            if (spf[p / 2] != 0)
                continue;
            long step = 2L * p;
            long start = (long) p * p;
            for (long j = start; j <= limit; j += step) {
                if (spf[(int) (j / 2)] == 0)
                    spf[(int) (j / 2)] = p;
            }
        }
        return spf;
    }

    static boolean checkN(int n, boolean[] isPrime, int[] spfOdd) {
        if (n == 1)
            return true;
        if ((n & 1) != 0)
            return false;
        if ((n & 3) == 0)
            return false;

        int m = n / 2;
        List<Integer> factors = new ArrayList<>();
        factors.add(2);
        while (m > 1) {
            int p = spfOdd[m / 2];
            if (p == 0)
                p = m;
            factors.add(p);
            m /= p;
            if (m % p == 0)
                return false;
        }

        List<Long> divisors = new ArrayList<>();
        divisors.add(1L);
        for (int p : factors) {
            int size = divisors.size();
            for (int i = 0; i < size; i++) {
                divisors.add(divisors.get(i) * p);
            }
        }

        for (long d : divisors) {
            long q = (long) n / d;
            if (d > q)
                continue;
            if (!isPrime[(int) (d + q)])
                return false;
        }
        return true;
    }

    public static String solve() {
        int limit = 100000000;
        int maxPrime = limit + 1;
        boolean[] isPrime = sievePrimes(maxPrime);

        List<Integer> primes = new ArrayList<>();
        if (maxPrime >= 2 && isPrime[2])
            primes.add(2);
        for (int i = 3; i <= maxPrime; i += 2) {
            if (isPrime[i])
                primes.add(i);
        }

        int half = limit / 2;
        int[] spfOdd = buildSpfOdd(half);

        int threads = Runtime.getRuntime().availableProcessors();
        if (threads <= 0)
            threads = 1;
        if (threads > primes.size())
            threads = primes.size();

        ExecutorService executor = Executors.newFixedThreadPool(threads);
        List<Future<Long>> futures = new ArrayList<>();

        int chunk = (primes.size() + threads - 1) / threads;
        for (int t = 0; t < threads; t++) {
            final int start = t * chunk;
            final int end = Math.min(primes.size(), start + chunk);
            futures.add(executor.submit(() -> {
                long local = 0;
                for (int i = start; i < end; i++) {
                    int n = primes.get(i) - 1;
                    if (n > limit)
                        continue;
                    if (checkN(n, isPrime, spfOdd)) {
                        local += n;
                    }
                }
                return local;
            }));
        }

        long total = 0;
        try {
            for (Future<Long> f : futures) {
                total += f.get();
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
        executor.shutdown();

        return String.valueOf(total);
    }

    public static void main(String[] args) {
        System.out.println(solve());
    }
}