Problem 347: Largest Integer Divisible by Two Primes

Project Euler Problem 347 Solution

EulerSolve provides an optimized solution for Project Euler Problem 347, Largest Integer Divisible by Two Primes, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary For each pair of distinct primes $p \lt q$, define $M(p,q,N)$ as the largest integer not exceeding $N$ whose only prime divisors are exactly $p$ and $q$, with both primes appearing at least once. In other words, valid numbers have the form $p^a q^b$ with $a,b \ge 1$. The goal is to compute $$S(N)=\sum_{p \lt q} M(p,q,N).$$ The key difficulty is that we must optimize over exponents for every prime pair, but we must do so without factoring every integer up to $N$. Mathematical Approach Fix distinct primes $p$ and $q$. Then $$M(p,q,N)=\max\{p^a q^b : a,b \ge 1,\ p^a q^b \le N\},$$ with the convention that $M(p,q,N)=0$ when no such exponents exist. Structure of the Admissible Numbers By the Fundamental Theorem of Arithmetic, every positive integer has a unique prime factorization. Therefore a number counted for the pair $(p,q)$ must be of the form $p^a q^b$ with no third prime factor. The smallest such number is $pq$, so immediately: $$pq \gt N \implies M(p,q,N)=0.$$ This simple observation is what allows both nested prime loops in the code to terminate early. Optimizing the Exponents for a Fixed Pair Suppose $p^a$ is fixed....

Detailed mathematical approach

Problem Summary

For two distinct primes $p$ and $q$, let $M(p,q,N)$ be the largest positive integer $n\le N$ divisible by $p$, by $q$ and by no other prime, and $M(p,q,N)=0$ if no such $n$ exists. The statement gives $M(2,3,100)=96=2^5\cdot3$; then $M(3,5,100)=75$, not $90$, because $90=2\cdot3^2\cdot5$ carries the extra prime $2$; and $M(2,73,100)=0$, since $2\cdot73=146$ already exceeds $100$. Writing $S(N)$ for the sum of all distinct values $M(p,q,N)$, we are given $S(100)=2262$ and must find $S(N)$ for $N=10\,000\,000$. ^[1] Since $M(p,q,N)=M(q,p,N)$, we always label the pair so that $p\lt q$, and count each unordered pair once.

The whole solution in one sentence: for every pair $p\lt q$ of primes whose product is at most $N$ we walk over the handful of numbers $p^aq^b\le N$ with $a,b\ge1$, keep the largest one, and add those maxima up.

Mathematical Approach

Two questions decide everything: which pairs contribute at all, and which exponents give the largest value. The first has a one-line answer; the second needs a short scan, because taking the smallest or the largest possible exponent of $p$ can miss the maximum.

1. Which numbers belong to a pair

By the fundamental theorem of arithmetic every integer greater than $1$ factors into primes in exactly one way. ^[2] So "divisible by $p$ and by $q$ and by no other prime" says precisely that $n=p^aq^b$ with integers $a,b\ge1$: both exponents are positive because both primes must divide $n$, and no third prime is allowed. For $p=3$, $q=5$, $N=100$ the admissible numbers are $15$, $45$, $75$ and nothing else; $90$ is barred because its factorisation contains a $2$. So, as long as one admissible number exists,

$$M(p,q,N)=\max\{p^aq^b\le N:a,b\ge1\},$$

and $M(p,q,N)=0$ otherwise, the case Section 2 settles.

2. When a pair contributes nothing

Every admissible number is a multiple of $pq$, while $pq$ is itself admissible as soon as $pq\le N$. So the set is empty exactly when $pq\gt N$:

$$M(p,q,N)\gt0\iff pq\le N.$$

The contributing pairs therefore correspond one to one with the squarefree semiprimes up to $N$, the products of two distinct primes. ^[6] There are $30$ below $100$ and $1\,903\,878$ below $10^7$.

3. Why the word "distinct" changes nothing

A nonzero value $m=p^aq^b$ has exactly $\{p,q\}$ as its set of prime divisors, so $m$ determines its pair and two different pairs can never give the same nonzero value. Only $0$ repeats, once per pair with $pq\gt N$, and it adds nothing. So $S(N)$ is just the sum of the maxima over the pairs with $pq\le N$.

4. The largest value hides in an unpredictable place

Group the admissible numbers by the power of $p$. For $p=2$, $q=3$, $N=100$ the rows are

$2\cdot3^b$: $6,18,54$;
$4\cdot3^b$: $12,36$;
$8\cdot3^b$: $24,72$;
$16\cdot3^b$: $48$, and $32\cdot3^b$: $96$.

The row maxima $54,36,72,48,96$ rise and fall, and the winner $M(2,3,100)=96$ sits in the last row. Neither endpoint is safe: for $(2,3)$ at $N=40$ the rows are $6,18$, then $12,36$, then $24$, with maxima $18,36,24$, so the middle row wins; and $(2,3)$ at $N=10^7$ has its maximum $2\cdot3^{14}=9\,565\,938$ in the first of $21$ rows.

The zigzag has a reason. Call a row non-empty when $p^aq\le N$, and for such a row let $B(a)$ be the largest integer $b\ge1$ with $p^aq^b\le N$, so the row maximum is $p^aq^{B(a)}$. Take two consecutive non-empty rows. Then $B(a+1)\le B(a)$, as a larger power of $p$ leaves less room, while $q^b\le N/p^a$ gives, because $p\lt q$,

$$q^{b-1}\le\frac{N}{p^aq}\le\frac{N}{p^{a+1}},$$

so $B(a+1)\ge B(a)-1$ whenever $B(a)\ge2$; for $B(a)=1$ it is trivial, since $B(a+1)\ge1$ by definition. The exponent of $q$ therefore falls by $0$ or $1$ from one row to the next, and consecutive row maxima differ by a factor of exactly $p$ or $p/q$. As $p\lt q$, one factor exceeds $1$ and the other does not: hence the zigzag, with ratios $2/3,2,2/3,2$ above. Both claims were checked in $595\,560$ cases $(N,p,q)$ — every contributing pair for each $N\le2000$, and for $N=10^4$, $10^5$.

5. The scan over the exponents

Within one row $a$ is fixed and $p^aq^b$ grows strictly with $b$, so only the largest admissible $b$ matters. With $A$ the largest $a\ge1$ satisfying $p^aq\le N$, the rows partition the admissible set, so

$$M(p,q,N)=\max_{1\le a\le A}p^a\,q^{B(a)}.$$

Both ranges are tiny. As $A$ and $B(a)$ are integers and $p\ge2$, $q\ge3$,

$$\begin{aligned}A&\le\lfloor\log_2(N/3)\rfloor,\\ B(a)&\le\lfloor\log_3(N/2)\rfloor,\end{aligned}$$

which at $N=10^7$ are $21$ and $14$; the pair $(2,3)$ attains both, as $2^{21}\cdot3=6\,291\,456$ fits while $2^{22}\cdot3$ does not, and $2\cdot3^{14}=9\,565\,938$ fits while $2\cdot3^{15}$ does not. So no pair has more than $21\cdot14=294$ candidates, the true maximum being $152$, again for $(2,3)$, while at that limit $81$ per cent of the pairs offer only $pq$.

6. Comparing products without overflow

The scan tests $vq\le N$ over and over. Inside a row the code never forms that product first; it divides instead, using the identity that for positive integers $v,q,L$,

$$vq\le L\iff v\le\lfloor L/q\rfloor.$$

Indeed $vq\le L$ gives $v\le L/q$, hence $v\le\lfloor L/q\rfloor$ as $v$ is an integer; conversely $v\le\lfloor L/q\rfloor$ gives $vq\le q\lfloor L/q\rfloor\le L$. One integer division, exact, and the next multiplication happens only once its result is known to be at most $L$. The separate tests that reject a whole pair do form $pq$ first, staying safe through a wider type: $64$-bit in C++ and Java, unbounded in Python.

7. What the scan really walks through

Over all pairs and rows the walk visits every admissible $p^aq^b\le N$ exactly once: none is skipped, as the rows run to $A$ and each row to $B(a)$, and none is seen twice, as its factorisation fixes the pair, the row and the step. By Section 1 these are exactly the integers up to $N$ with two distinct prime divisors. ^[5] For $N=24$ the walk gives $6,10,12,14,15,18,20,21,22,24$. The cost of the double loop is thus an exact count, not an estimate: $2\,536\,838$ steps at $N=10^7$.

8. The worked example $S(100)$

Exactly $30$ pairs satisfy $pq\le100$, with maxima

$p=2$: $q=3,5,7,11,13$ give $96,100,98,88,52$; $q=17,19,23,29,31$ give $68,76,92,58,62$; $q=37,41,43,47$ give $74,82,86,94$;
$p=3$: $q=5,7,11,13,17$ give $75,63,99,39,51$; $q=19,23,29,31$ give $57,69,87,93$;
$p=5$: $q=7,11,13,17,19$ give $35,55,65,85,95$;
$p=7$: $q=11,13$ give $77,91$.

All thirty differ and add up to $2262$, the checkpoint of the statement. Two repay a look: $M(2,5,100)=2^2\cdot5^2=100$ meets the bound exactly, and $M(3,11,100)=3^2\cdot11=99$ beats $M(3,13,100)=3\cdot13=39$, so the maxima are not monotone in $q$ either.

9. Two bounds, and the size of the sum

Let $m=M(p,q,N)\gt0$. Both $mp$ and $mq$ are again of the shape $p^aq^b$ with $a,b\ge1$, and $m$ is the largest such number up to $N$, so $mp\gt N$ and $mq\gt N$, giving

$$M(p,q,N)\gt N/p.$$

Every maximum therefore lies within a factor $p$ of the bound, and exceeds $N/2$ when $p=2$. That fixes the size of the answer without computing it: the $348\,512$ pairs $(2,q)$ with $q$ an odd prime up to $5\cdot10^6$ each contribute more than $5\cdot10^6$, so $S(10^7)$ exceeds $1.74\cdot10^{12}$, while the $1\,903\,878$ maxima, none above $10^7$, total less than $1.91\cdot10^{13}$. A $32$-bit accumulator would overflow; a signed $64$-bit one, good to $9.2\cdot10^{18}$, cannot.

How the Code Works

All three programs share three stages: sieve, pair loop, exponent maximum. C++ sieves in sieve_primes(limit), Java in sievePrimes(limit), Python inline inside solve() — all by the classical sieve of Eratosthenes: ^[3] walk $i$ upwards, record $i$ as prime whenever its flag is clear, then mark $i^2,i^2+i,\dots$ — from $i^2$, because a smaller multiple of $i$ has a prime factor below $i$ and was marked already, and only while $i\le\sqrt{N}$, because every composite $n\le N$ has a prime factor at most $\sqrt{n}$. The guard i <= limit / i tests $i^2\le N$ without forming $i^2$, which as an int overflows above $i=46\,340$. The flags are a bit-packed std::vector<bool>, a boolean[] (one byte per entry in common runtimes) and a bytearray.

The scan is max_for_pair(p, q, limit) in C++, maxForPair in Java and a nested max_for_pair(p, q) in Python taking limit from the enclosing solve(); all three are Sections 5 and 6 verbatim. The outer loop holds pa $=p^a$ and runs while pa <= limit / q, that is $p^aq\le N$, enumerating the rows. Each row starts at value = pa * q and multiplies by $q$ while value <= limit / q, updating best each time although only a row's last value can win. The opening test p * q > limit returns $0$ at once: redundant, as the outer loop would not run, but it states Section 2. The closing test pa > limit / p keeps pa *= p in range.

C++ passes the bound to solve(limit), while the Java and Python solve() fix it internally. Each runs the double loop over the prime list, index i for $p$ and j > i for $q$ — this is where $p\lt q$ is enforced — the inner loop breaking at the first $q$ with $pq\gt N$, sound because the list increases. The outer loop breaks when $2p\gt N$, correct but weak: only primes with $p^2\lt N$ can open a pair, so it could stop at $p\gt3162$, yet it visits all $348\,513$ primes up to $5\cdot10^6$, the $348\,067$ above $3162$ doing one test before breaking. Before adding a maximum, solve checks a byte array seen and skips a value already added; by Section 3 that cannot happen, and at $N=10^7$ the guard never fires. It is a literal reading of "all distinct", at a cost of $10$ MB.

The C++ file carries the self-checks. brute_solve(limit) factorises every $n\le$ limit by trial division, drops $n$ once a third distinct prime appears and keeps the largest $n$ per pair; run_checkpoints verifies the three values of the statement, $S(100)=2262$, and that solve(300) and brute_solve(300) agree. main accepts --limit= and --skip-checkpoints, but its digit loop accumulates the limit in an int with no range test, so an argument of $2^{31}$ or more overflows, as a sanitizer build reports; the default is far from that. Java and Python package no checks. C++ keeps powers, maxima and sum in the unsigned alias u64, Java in a signed long, both wide enough by Section 9; Java's List<Integer> unwraps an object on every access, and Python's unbounded integers make the width question moot. ^[8]

Complexity and Verification

The sieve costs $O(N\log\log N)$ time and $O(N)$ memory ^[3] and yields $\pi(10^7)=664\,579$ primes, $\pi$ being the prime-counting function. ^[4] The pair stage is $O(N)$: by Section 7 each inner step owns a different integer $\le N$, so there are at most $N$ of them, and every non-empty row and contributing pair holds at least one; the at most $\pi(N)$ outer iterations add one failed test each at worst; clearing seen is $O(N)$. The total is thus the sieve's $O(N\log\log N)$. Measured at $N=10^7$: $2\,536\,838$ inner steps in $2\,530\,667$ rows, the most rows for one pair being $21$, for $(2,3)$. The pair count $1\,903\,878$ came twice over — from the loop, and as the squarefree semiprimes up to $10^7$ by binary search over the prime list. ^[6] Landau's theorem counts integers with two prime factors with multiplicity, $1\,904\,324$ here, with leading term $N\log\log N/\log N$, about $1.72\cdot10^6$ at $N=10^7$. ^[7] Our pairs are that count less the $\pi(\sqrt N)=446$ prime squares, a correction below $\sqrt N$ that cannot touch the leading term, so the pair count grows at the same rate, slowly as it is approached.

In C++ the payloads are $1.25$ MB of sieve bits, $2.66$ MB for the $32$-bit prime list and $10$ MB for seen; the sieve flags are freed before seen is allocated, so the three never coexist. Python's byte arrays and integer objects and Java's boxed prime list cost more, and both carry a runtime, so peak process memory is a multiple of the payload. The storage is $O(N)$ throughout, and all three runs take about a second or less.

Beyond the packaged checks, these were run for this article.

A brute force factorising every integer matches the pair loop for every $N$ from $2$ to $600$; the packaged check at $N=300$ gives $18069$ both ways. Up to $N=3000$ the distinct maxima and the per-pair maxima sum alike, none repeating (Section 3).
Checkpoints computed twice, independently: $S(1000)=193408$, $S(10^4)=16373230$, $S(10^5)=1414000891$, $S(10^6)=124397236942$.
At $N=10^7$, smallest- and largest-prime-factor sieves give both primes of every integer with two distinct prime divisors; the largest per pair, taken by sorting, sums to the pair loop's value and confirms the $1\,903\,878$ distinct maxima.
For $N=24$, $100$, $1000$ the inner loop visits exactly those integers, once each; $mp\gt N$ and $mq\gt N$ hold for every pair at $N=10^7$ and every $N\le3000$; the three programs print the same value.

Footnotes and References

The sources below supply the background facts; Sections 4, 7 and 9 are derived here.

Project Euler 347 — Largest Integer Divisible by Two Primes. The official statement defines M(p, q, N) as the largest positive integer up to N divisible by both distinct primes p and q and by nothing else, 0 when none exists, gives M(2, 3, 100) = 96, M(3, 5, 100) = 75 and M(2, 73, 100) = 0, and asks for the sum S(N) of all distinct M(p, q, N) at N = 10 000 000, with S(100) = 2262 as checkpoint.
Wikipedia — Fundamental theorem of arithmetic. Every integer greater than 1 factors into primes uniquely apart from the order of the factors, so each prime's multiplicity is fixed; Sections 1 and 3 rest on this.
Wikipedia — Sieve of Eratosthenes. It gives the time O(n log log n) for an O(1) array update, O(n) memory, and notes that marking may start at p squared.
Wikipedia — Prime-counting function. Its table of known values lists π(10⁷) = 664 579, the length of the prime list the solutions build.
OEIS A007774 — numbers divisible by exactly 2 different primes. The integers n with ω(n) = 2; its first ten terms are the ten numbers Section 7 obtains for N = 24.
OEIS A006881 — squarefree semiprimes. The products of two distinct primes; by Section 2 the contributing pairs match its terms up to N.
Wikipedia — Almost prime. It states Landau's result (Handbuch der Lehre von der Verteilung der Primzahlen, 1909) that the count of integers up to n with exactly k prime factors, counted with multiplicity, is asymptotically (n / log n)·(log log n)^(k−1)/(k−1)!, which for k = 2 is n log log n / log n.
C++ — Euler347.cpp. The linked immutable revision holds sieve_primes, max_for_pair, solve, brute_solve and run_checkpoints; it is the implementation record for this article.

Problem 347 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <unordered_map>
#include <vector>

namespace {

using u64 = std::uint64_t;

struct Options {
    int limit = 10'000'000;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }
    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);
        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--limit=", options.limit)) {
            continue;
        }
        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }
    return options.limit >= 2;
}

std::vector<int> sieve_primes(const int limit) {
    std::vector<bool> is_composite(static_cast<std::size_t>(limit + 1), false);
    std::vector<int> primes;
    for (int i = 2; i <= limit; ++i) {
        if (!is_composite[static_cast<std::size_t>(i)]) {
            primes.push_back(i);
            if (i <= limit / i) {
                for (int j = i * i; j <= limit; j += i) {
                    is_composite[static_cast<std::size_t>(j)] = true;
                }
            }
        }
    }
    return primes;
}

u64 max_for_pair(const int p, const int q, const int limit) {
    if (static_cast<u64>(p) * static_cast<u64>(q) > static_cast<u64>(limit)) {
        return 0ULL;
    }
    u64 best = 0ULL;
    for (u64 pa = static_cast<u64>(p); pa <= static_cast<u64>(limit / q);) {
        u64 value = pa * static_cast<u64>(q);
        while (value <= static_cast<u64>(limit)) {
            best = std::max(best, value);
            if (value > static_cast<u64>(limit / q)) {
                break;
            }
            value *= static_cast<u64>(q);
        }
        if (pa > static_cast<u64>(limit / p)) {
            break;
        }
        pa *= static_cast<u64>(p);
    }
    return best;
}

u64 solve(const int limit) {
    const std::vector<int> primes = sieve_primes(limit);
    std::vector<unsigned char> seen(static_cast<std::size_t>(limit + 1), 0U);

    u64 sum = 0ULL;
    for (std::size_t i = 0; i < primes.size(); ++i) {
        const int p = primes[i];
        if (static_cast<u64>(p) * 2ULL > static_cast<u64>(limit)) {
            break;
        }
        for (std::size_t j = i + 1; j < primes.size(); ++j) {
            const int q = primes[j];
            if (static_cast<u64>(p) * static_cast<u64>(q) > static_cast<u64>(limit)) {
                break;
            }
            const u64 m = max_for_pair(p, q, limit);
            if (m > 0ULL && seen[static_cast<std::size_t>(m)] == 0U) {
                seen[static_cast<std::size_t>(m)] = 1U;
                sum += m;
            }
        }
    }
    return sum;
}

u64 brute_solve(const int limit) {
    std::unordered_map<u64, int> best_by_pair;
    for (int n = 2; n <= limit; ++n) {
        int x = n;
        std::vector<int> distinct_primes;
        for (int p = 2; p <= x / p; ++p) {
            if (x % p != 0) {
                continue;
            }
            distinct_primes.push_back(p);
            while (x % p == 0) {
                x /= p;
            }
            if (distinct_primes.size() > 2U) {
                break;
            }
        }
        if (distinct_primes.size() <= 2U && x > 1) {
            distinct_primes.push_back(x);
        }
        if (distinct_primes.size() == 2U) {
            int p = distinct_primes[0];
            int q = distinct_primes[1];
            if (p > q) {
                std::swap(p, q);
            }
            const u64 key = (static_cast<u64>(static_cast<std::uint32_t>(p)) << 32U) |
                            static_cast<u64>(static_cast<std::uint32_t>(q));
            auto it = best_by_pair.find(key);
            if (it == best_by_pair.end() || n > it->second) {
                best_by_pair[key] = n;
            }
        }
    }

    std::vector<unsigned char> seen(static_cast<std::size_t>(limit + 1), 0U);
    u64 sum = 0ULL;
    for (const auto& entry : best_by_pair) {
        const int value = entry.second;
        if (seen[static_cast<std::size_t>(value)] == 0U) {
            seen[static_cast<std::size_t>(value)] = 1U;
            sum += static_cast<u64>(value);
        }
    }
    return sum;
}

bool run_checkpoints() {
    if (max_for_pair(2, 3, 100) != 96ULL) {
        std::cerr << "Checkpoint failed for M(2,3,100)" << '\n';
        return false;
    }
    if (max_for_pair(3, 5, 100) != 75ULL) {
        std::cerr << "Checkpoint failed for M(3,5,100)" << '\n';
        return false;
    }
    if (max_for_pair(2, 73, 100) != 0ULL) {
        std::cerr << "Checkpoint failed for M(2,73,100)" << '\n';
        return false;
    }
    if (solve(100) != 2262ULL) {
        std::cerr << "Checkpoint failed for S(100)" << '\n';
        return false;
    }
    if (solve(300) != brute_solve(300)) {
        std::cerr << "Checkpoint failed for brute-force cross-check at N=300" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }
    std::cout << solve(options.limit) << '\n';
    return 0;
}

Python

def solve():
    limit = 10_000_000

    # Sieve primes
    is_composite = bytearray(limit + 1)
    primes = []
    for i in range(2, limit + 1):
        if not is_composite[i]:
            primes.append(i)
            if i <= limit // i:
                for j in range(i*i, limit + 1, i):
                    is_composite[j] = 1

    def max_for_pair(p, q):
        if p * q > limit:
            return 0
        best = 0
        pa = p
        while pa <= limit // q:
            value = pa * q
            while value <= limit:
                if value > best:
                    best = value
                if value > limit // q:
                    break
                value *= q
            if pa > limit // p:
                break
            pa *= p
        return best

    seen = bytearray(limit + 1)
    total = 0
    for i in range(len(primes)):
        p = primes[i]
        if p * 2 > limit:
            break
        for j in range(i + 1, len(primes)):
            q = primes[j]
            if p * q > limit:
                break
            m = max_for_pair(p, q)
            if m > 0 and not seen[m]:
                seen[m] = 1
                total += m

    return str(total)

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

Java

import java.util.*;

public class Euler347 {

    static List<Integer> sievePrimes(int limit) {
        boolean[] isComposite = new boolean[limit + 1];
        List<Integer> primes = new ArrayList<>();

        for (int i = 2; i <= limit; i++) {
            if (!isComposite[i]) {
                primes.add(i);
                if (i <= limit / i) {
                    for (int j = i * i; j <= limit; j += i) {
                        isComposite[j] = true;
                    }
                }
            }
        }
        return primes;
    }

    static long maxForPair(int p, int q, int limit) {
        if ((long) p * q > limit)
            return 0;

        long best = 0;
        for (long pa = p; pa <= limit / q;) {
            long value = pa * q;
            while (value <= limit) {
                best = Math.max(best, value);
                if (value > limit / q)
                    break;
                value *= q;
            }
            if (pa > limit / p)
                break;
            pa *= p;
        }
        return best;
    }

    public static String solve() {
        int limit = 10000000;
        List<Integer> primes = sievePrimes(limit);
        byte[] seen = new byte[limit + 1];
        long sum = 0;

        for (int i = 0; i < primes.size(); i++) {
            int p = primes.get(i);
            if ((long) p * 2L > limit)
                break;

            for (int j = i + 1; j < primes.size(); j++) {
                int q = primes.get(j);
                if ((long) p * q > limit)
                    break;

                long m = maxForPair(p, q, limit);
                if (m > 0 && seen[(int) m] == 0) {
                    seen[(int) m] = 1;
                    sum += m;
                }
            }
        }
        return String.valueOf(sum);
    }

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