Problem 1005: Median Prime List

Project Euler Problem 1005 Solution

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

Problem Summary We consider all lists of strictly increasing primes whose sum is a target $N$. These lists are sorted in lexicographic order, and the required list is the median list. When the number of lists is even, the last list is ignored first; equivalently, if there are $M$ lists, the required one has one-based rank $$r=\left\lfloor\frac{M+1}{2}\right\rfloor.$$ For $N=20$, the four lists are $(2,5,13)$, $(2,7,11)$, $(3,17)$, and $(7,13)$. Since $M=4$, the effective median rank is $2$, giving $(2,7,11)$. The actual problem asks for $N=2026$, and only the last nine digits of the product of the primes in the median list are needed. Mathematical Approach Prime lists are subsets with a canonical order Because every list is strictly increasing, each valid list is exactly a subset of the primes not exceeding $N$, written in increasing order, whose elements sum to $N$. If $$p_0 \lt p_1 \lt \cdots \lt p_{m-1}$$ are the primes at most $N$, the problem is not to enumerate every subset, but to count enough subsets to jump directly to the median in lexicographic order. The strict increase is important: after choosing $p_i$, every later prime in the same list must come from $p_{i+1},p_{i+2},\dots$. This creates a natural suffix dynamic program....

Detailed mathematical approach

Problem Summary

We consider all lists of strictly increasing primes whose sum is a target $N$. These lists are sorted in lexicographic order, and the required list is the median list. When the number of lists is even, the last list is ignored first; equivalently, if there are $M$ lists, the required one has one-based rank

$$r=\left\lfloor\frac{M+1}{2}\right\rfloor.$$

For $N=20$, the four lists are $(2,5,13)$, $(2,7,11)$, $(3,17)$, and $(7,13)$. Since $M=4$, the effective median rank is $2$, giving $(2,7,11)$. The actual problem asks for $N=2026$, and only the last nine digits of the product of the primes in the median list are needed.

Mathematical Approach

Prime lists are subsets with a canonical order

Because every list is strictly increasing, each valid list is exactly a subset of the primes not exceeding $N$, written in increasing order, whose elements sum to $N$. If

$$p_0 \lt p_1 \lt \cdots \lt p_{m-1}$$

are the primes at most $N$, the problem is not to enumerate every subset, but to count enough subsets to jump directly to the median in lexicographic order.

The strict increase is important: after choosing $p_i$, every later prime in the same list must come from $p_{i+1},p_{i+2},\dots$. This creates a natural suffix dynamic program.

Counting completions from a suffix

Define

$$C(i,s)=\#\left\{A\subseteq\{p_i,p_{i+1},\dots,p_{m-1}\}:\sum_{p\in A}p=s\right\}.$$

The boundary condition is

$$C(m,0)=1,\qquad C(m,s)=0\quad(s\gt0).$$

For $i\lt m$, either $p_i$ is skipped or it is used. Therefore

$$C(i,s)=C(i+1,s)+ \begin{cases} C(i+1,s-p_i), & s\ge p_i,\\ 0, & s\lt p_i. \end{cases}$$

This is the subset-sum recurrence, but the table is used as a ranking oracle rather than just as a yes/no feasibility test. The total number of prime lists is $M=C(0,N)$. These counts can be large, so the implementations use arbitrary-precision integers for the DP table.

Why suffix counts match lexicographic blocks

In lexicographic order, all lists whose first element is $p_a$ appear before all lists whose first element is $p_b$ whenever $p_a\lt p_b$. If we try a candidate first prime $p_i$, the number of lists beginning with that prime is exactly

$$C(i+1,N-p_i),$$

because the remaining entries must be chosen from strictly larger primes and must sum to $N-p_i$. Thus each candidate first prime forms one contiguous lexicographic block.

The same idea applies after a prefix has already been fixed. If the current prefix ends at index $i$, the next candidate $p_j$ contributes a block of size

$$C(j+1,R-p_j).$$

This block size tells us whether the desired rank lies inside that block or after it.

Unranking the median list

Set $r=\lfloor(M+1)/2\rfloor$. Start with remaining sum $N$ and the first allowable prime index $0$. Scan candidate primes in increasing order. For a candidate $p_i$, compute

$$B_i=C(i+1,R-p_i).$$

If $r>B_i$, the whole block beginning with $p_i$ is before the median, so subtract it:

$$r\leftarrow r-B_i.$$

If $r\le B_i$, the median list begins, or continues, with $p_i$. Append $p_i$, decrease the remaining sum by $p_i$, and continue with candidates after $i$. When the remaining sum becomes $0$, the list has been reconstructed without enumerating all lists.

Worked example: $N=20$

The DP gives $C(0,20)=4$, so $r=\lfloor(4+1)/2\rfloor=2$. The first candidate $2$ has

$$C(1,18)=2,$$

corresponding to $(2,5,13)$ and $(2,7,11)$. Since $r=2$ lies inside this block, the first element is $2$.

Now the remaining sum is $18$. Candidate $3$ has no valid completion, candidate $5$ has one completion $(13)$, and candidate $7$ has one completion $(11)$. After skipping the block for $5$, the rank becomes $1$, so $7$ is selected. The final remaining sum is $11$, forcing the last prime $11$. Hence the median list is $(2,7,11)$.

How the Code Works

primes_up_to builds the prime list by a sieve. build_dp fills the suffix table $C(i,s)$ from the last prime backward, using arbitrary-precision counts because the number of prime subsets can exceed fixed-width integer ranges.

kth_prime_list performs the lexicographic unranking. For each candidate prime it asks the DP table how many valid completions exist. Entire blocks are skipped by subtracting their sizes from the rank; the first block containing the rank determines the next prime in the answer.

median_prime_list converts the total count into the median rank $(M+1)//2$. Finally product_mod multiplies the selected primes modulo $10^9$, which is enough because only the last nine digits are requested.

The checkpoint suite explicitly checks the $N=20$ example and brute-forces every target from $2$ through $60$, verifying that the DP count, first rank, median rank, and last rank all match direct enumeration.

Complexity Analysis

Let $m=\pi(N)$, the number of primes at most $N$. The DP table has $(m+1)(N+1)$ entries and is filled in $O(mN)$ arithmetic operations. The unranking pass scans primes at each selected position, bounded by $O(mL)$, where $L$ is the length of the median list; this is dominated by the DP for the given target.

The memory usage is $O(mN)$ arbitrary-precision integers. For $N=2026$, $m=306$, so the table is small in practical terms.

Footnotes and References

Problem page: Project Euler 1005 - Median Prime List
Subset sum problem: Wikipedia - Subset sum problem
Dynamic programming: Wikipedia - Dynamic programming
Lexicographic order: Wikipedia - Lexicographic order
Sieve of Eratosthenes: Wikipedia - Sieve of Eratosthenes

Problem 1005 source code

C++

#include <algorithm>
#include <boost/multiprecision/cpp_int.hpp>
#include <cstdint>
#include <cstdlib>
#include <iomanip>
#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

namespace {

using boost::multiprecision::cpp_int;
using i64 = std::int64_t;

constexpr int kDefaultTarget = 2026;
constexpr i64 kMod = 1'000'000'000LL;

struct Options {
    int target = kDefaultTarget;
    bool run_checkpoints = true;
};

struct PrimeDp {
    int target = 0;
    std::vector<int> primes;
    std::vector<std::vector<cpp_int>> suffix_count;
};

std::vector<int> primes_up_to(const int limit) {
    if (limit < 2) {
        return {};
    }

    std::vector<bool> composite(static_cast<std::size_t>(limit + 1), false);
    for (int p = 2; p * p <= limit; ++p) {
        if (!composite[static_cast<std::size_t>(p)]) {
            for (int multiple = p * p; multiple <= limit; multiple += p) {
                composite[static_cast<std::size_t>(multiple)] = true;
            }
        }
    }

    std::vector<int> primes;
    for (int value = 2; value <= limit; ++value) {
        if (!composite[static_cast<std::size_t>(value)]) {
            primes.push_back(value);
        }
    }
    return primes;
}

PrimeDp build_dp(const int target) {
    PrimeDp dp;
    dp.target = target;
    dp.primes = primes_up_to(target);
    const int count = static_cast<int>(dp.primes.size());
    dp.suffix_count.assign(static_cast<std::size_t>(count + 1),
                           std::vector<cpp_int>(static_cast<std::size_t>(target + 1), 0));
    dp.suffix_count[static_cast<std::size_t>(count)][0] = 1;

    for (int i = count - 1; i >= 0; --i) {
        const int prime = dp.primes[static_cast<std::size_t>(i)];
        for (int sum = 0; sum <= target; ++sum) {
            cpp_int ways = dp.suffix_count[static_cast<std::size_t>(i + 1)][static_cast<std::size_t>(sum)];
            if (sum >= prime) {
                ways += dp.suffix_count[static_cast<std::size_t>(i + 1)][static_cast<std::size_t>(sum - prime)];
            }
            dp.suffix_count[static_cast<std::size_t>(i)][static_cast<std::size_t>(sum)] = ways;
        }
    }

    return dp;
}

std::vector<int> kth_prime_list(const PrimeDp& dp, cpp_int rank) {
    if (rank <= 0 || rank > dp.suffix_count[0][static_cast<std::size_t>(dp.target)]) {
        throw std::runtime_error("Requested rank is outside the available prime lists");
    }

    int remaining = dp.target;
    int start = 0;
    std::vector<int> result;

    while (remaining > 0) {
        bool found = false;
        for (int i = start; i < static_cast<int>(dp.primes.size()); ++i) {
            const int prime = dp.primes[static_cast<std::size_t>(i)];
            if (prime > remaining) {
                break;
            }

            const cpp_int& block =
                dp.suffix_count[static_cast<std::size_t>(i + 1)][static_cast<std::size_t>(remaining - prime)];
            if (rank > block) {
                rank -= block;
                continue;
            }

            result.push_back(prime);
            remaining -= prime;
            start = i + 1;
            found = true;
            break;
        }

        if (!found) {
            throw std::runtime_error("Could not unrank the requested prime list");
        }
    }

    return result;
}

std::vector<int> median_prime_list(const PrimeDp& dp) {
    const cpp_int total = dp.suffix_count[0][static_cast<std::size_t>(dp.target)];
    if (total == 0) {
        throw std::runtime_error("There is no prime list for the requested target");
    }
    return kth_prime_list(dp, (total + 1) / 2);
}

i64 product_mod(const std::vector<int>& values) {
    i64 product = 1;
    for (const int value : values) {
        product = product * value % kMod;
    }
    return product;
}

void enumerate_bruteforce(const std::vector<int>& primes,
                          const int start,
                          const int remaining,
                          std::vector<int>& current,
                          std::vector<std::vector<int>>& lists) {
    if (remaining == 0) {
        lists.push_back(current);
        return;
    }

    for (int i = start; i < static_cast<int>(primes.size()); ++i) {
        const int prime = primes[static_cast<std::size_t>(i)];
        if (prime > remaining) {
            break;
        }
        current.push_back(prime);
        enumerate_bruteforce(primes, i + 1, remaining - prime, current, lists);
        current.pop_back();
    }
}

std::vector<std::vector<int>> brute_lists(const int target) {
    std::vector<std::vector<int>> lists;
    std::vector<int> current;
    const std::vector<int> primes = primes_up_to(target);
    enumerate_bruteforce(primes, 0, target, current, lists);
    return lists;
}

void require_checkpoint(const bool ok, const std::string& message) {
    if (!ok) {
        std::cerr << "Checkpoint failed: " << message << '\n';
        std::exit(EXIT_FAILURE);
    }
}

void run_checkpoints() {
    {
        const PrimeDp dp = build_dp(20);
        const std::vector<std::vector<int>> expected{{2, 5, 13}, {2, 7, 11}, {3, 17}, {7, 13}};
        require_checkpoint(brute_lists(20) == expected, "lexicographic lists for 20");
        require_checkpoint(dp.suffix_count[0][20] == 4, "count for 20");
        require_checkpoint(median_prime_list(dp) == std::vector<int>({2, 7, 11}), "median list for 20");
        require_checkpoint(product_mod(median_prime_list(dp)) == 154, "product for 20");
    }

    for (int target = 2; target <= 60; ++target) {
        const PrimeDp dp = build_dp(target);
        const std::vector<std::vector<int>> lists = brute_lists(target);
        require_checkpoint(dp.suffix_count[0][static_cast<std::size_t>(target)] == lists.size(),
                           "DP count matches brute force for " + std::to_string(target));

        if (!lists.empty()) {
            const std::vector<int> median = median_prime_list(dp);
            require_checkpoint(median == lists[(lists.size() - 1) / 2],
                               "median matches brute force for " + std::to_string(target));

            const std::vector<int> first = kth_prime_list(dp, 1);
            const std::vector<int> middle = kth_prime_list(dp, cpp_int((lists.size() + 1) / 2));
            const std::vector<int> last = kth_prime_list(dp, cpp_int(lists.size()));
            require_checkpoint(first == lists.front(), "first rank for " + std::to_string(target));
            require_checkpoint(middle == lists[(lists.size() - 1) / 2],
                               "middle rank for " + std::to_string(target));
            require_checkpoint(last == lists.back(), "last rank for " + std::to_string(target));
        }
    }

    std::cerr << "Validation checkpoints passed.\n";
}

bool parse_arguments(const 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 (!arg.empty() && arg[0] == '-') {
            std::cerr << "Unknown option: " << arg << '\n';
            return false;
        }
        options.target = std::stoi(arg);
    }

    if (options.target < 0) {
        std::cerr << "Target must be nonnegative.\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();
    }

    try {
        const PrimeDp dp = build_dp(options.target);
        const std::vector<int> median = median_prime_list(dp);
        std::cout << std::setw(9) << std::setfill('0') << product_mod(median) << '\n';
    } catch (const std::exception& ex) {
        std::cerr << ex.what() << '\n';
        return 2;
    }

    return 0;
}

Python

#!/usr/bin/env python3
"""Project Euler Problem 1005 - Median Prime List."""

from __future__ import annotations

import argparse
from dataclasses import dataclass

DEFAULT_TARGET = 2026
MOD = 1_000_000_000


@dataclass
class PrimeDp:
    target: int
    primes: list[int]
    suffix_count: list[list[int]]


def primes_up_to(limit: int) -> list[int]:
    if limit < 2:
        return []

    composite = [False] * (limit + 1)
    p = 2
    while p * p <= limit:
        if not composite[p]:
            for multiple in range(p * p, limit + 1, p):
                composite[multiple] = True
        p += 1

    return [value for value in range(2, limit + 1) if not composite[value]]


def build_dp(target: int) -> PrimeDp:
    primes = primes_up_to(target)
    count = len(primes)
    suffix_count = [[0] * (target + 1) for _ in range(count + 1)]
    suffix_count[count][0] = 1

    for i in range(count - 1, -1, -1):
        prime = primes[i]
        next_row = suffix_count[i + 1]
        row = suffix_count[i]
        for total in range(target + 1):
            ways = next_row[total]
            if total >= prime:
                ways += next_row[total - prime]
            row[total] = ways

    return PrimeDp(target=target, primes=primes, suffix_count=suffix_count)


def kth_prime_list(dp: PrimeDp, rank: int) -> list[int]:
    total = dp.suffix_count[0][dp.target]
    if rank <= 0 or rank > total:
        raise ValueError("requested rank is outside the available prime lists")

    remaining = dp.target
    start = 0
    result: list[int] = []

    while remaining > 0:
        found = False
        for i in range(start, len(dp.primes)):
            prime = dp.primes[i]
            if prime > remaining:
                break

            block = dp.suffix_count[i + 1][remaining - prime]
            if rank > block:
                rank -= block
                continue

            result.append(prime)
            remaining -= prime
            start = i + 1
            found = True
            break

        if not found:
            raise RuntimeError("could not unrank the requested prime list")

    return result


def median_prime_list(dp: PrimeDp) -> list[int]:
    total = dp.suffix_count[0][dp.target]
    if total == 0:
        raise ValueError("there is no prime list for the requested target")
    return kth_prime_list(dp, (total + 1) // 2)


def product_mod(values: list[int]) -> int:
    product = 1
    for value in values:
        product = product * value % MOD
    return product


def enumerate_bruteforce(
    primes: list[int],
    start: int,
    remaining: int,
    current: list[int],
    lists: list[list[int]],
) -> None:
    if remaining == 0:
        lists.append(current.copy())
        return

    for i in range(start, len(primes)):
        prime = primes[i]
        if prime > remaining:
            break
        current.append(prime)
        enumerate_bruteforce(primes, i + 1, remaining - prime, current, lists)
        current.pop()


def brute_lists(target: int) -> list[list[int]]:
    lists: list[list[int]] = []
    enumerate_bruteforce(primes_up_to(target), 0, target, [], lists)
    return lists


def run_checkpoints() -> None:
    dp20 = build_dp(20)
    expected = [[2, 5, 13], [2, 7, 11], [3, 17], [7, 13]]
    assert brute_lists(20) == expected
    assert dp20.suffix_count[0][20] == 4
    assert median_prime_list(dp20) == [2, 7, 11]
    assert product_mod(median_prime_list(dp20)) == 154

    for target in range(2, 61):
        dp = build_dp(target)
        lists = brute_lists(target)
        assert dp.suffix_count[0][target] == len(lists)

        if lists:
            assert median_prime_list(dp) == lists[(len(lists) - 1) // 2]
            assert kth_prime_list(dp, 1) == lists[0]
            assert kth_prime_list(dp, (len(lists) + 1) // 2) == lists[(len(lists) - 1) // 2]
            assert kth_prime_list(dp, len(lists)) == lists[-1]


def parse_args() -> argparse.Namespace:
    parser = argparse.ArgumentParser(description="Solve Project Euler Problem 1005.")
    parser.add_argument("target", nargs="?", type=int, default=DEFAULT_TARGET)
    parser.add_argument("--skip-checkpoints", action="store_true")
    return parser.parse_args()


def main() -> None:
    args = parse_args()
    if args.target < 0:
        raise SystemExit("target must be nonnegative")

    if not args.skip_checkpoints:
        run_checkpoints()

    dp = build_dp(args.target)
    print(f"{product_mod(median_prime_list(dp)):09d}")


if __name__ == "__main__":
    main()

Java

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Euler1005 {
    private static final int DEFAULT_TARGET = 2026;
    private static final long MOD = 1_000_000_000L;

    private static final class Options {
        int target = DEFAULT_TARGET;
        boolean runCheckpoints = true;
    }

    private static final class PrimeDp {
        int target;
        List<Integer> primes;
        BigInteger[][] suffixCount;
    }

    private static List<Integer> primesUpTo(int limit) {
        List<Integer> primes = new ArrayList<>();
        if (limit < 2) {
            return primes;
        }

        boolean[] composite = new boolean[limit + 1];
        for (int p = 2; p * p <= limit; ++p) {
            if (!composite[p]) {
                for (int multiple = p * p; multiple <= limit; multiple += p) {
                    composite[multiple] = true;
                }
            }
        }

        for (int value = 2; value <= limit; ++value) {
            if (!composite[value]) {
                primes.add(value);
            }
        }
        return primes;
    }

    private static PrimeDp buildDp(int target) {
        PrimeDp dp = new PrimeDp();
        dp.target = target;
        dp.primes = primesUpTo(target);
        int count = dp.primes.size();
        dp.suffixCount = new BigInteger[count + 1][target + 1];
        for (int i = 0; i <= count; ++i) {
            Arrays.fill(dp.suffixCount[i], BigInteger.ZERO);
        }
        dp.suffixCount[count][0] = BigInteger.ONE;

        for (int i = count - 1; i >= 0; --i) {
            int prime = dp.primes.get(i);
            for (int sum = 0; sum <= target; ++sum) {
                BigInteger ways = dp.suffixCount[i + 1][sum];
                if (sum >= prime) {
                    ways = ways.add(dp.suffixCount[i + 1][sum - prime]);
                }
                dp.suffixCount[i][sum] = ways;
            }
        }

        return dp;
    }

    private static List<Integer> kthPrimeList(PrimeDp dp, BigInteger rank) {
        BigInteger total = dp.suffixCount[0][dp.target];
        if (rank.compareTo(BigInteger.ZERO) <= 0 || rank.compareTo(total) > 0) {
            throw new IllegalArgumentException("requested rank is outside the available prime lists");
        }

        int remaining = dp.target;
        int start = 0;
        List<Integer> result = new ArrayList<>();

        while (remaining > 0) {
            boolean found = false;
            for (int i = start; i < dp.primes.size(); ++i) {
                int prime = dp.primes.get(i);
                if (prime > remaining) {
                    break;
                }

                BigInteger block = dp.suffixCount[i + 1][remaining - prime];
                if (rank.compareTo(block) > 0) {
                    rank = rank.subtract(block);
                    continue;
                }

                result.add(prime);
                remaining -= prime;
                start = i + 1;
                found = true;
                break;
            }

            if (!found) {
                throw new IllegalStateException("could not unrank the requested prime list");
            }
        }

        return result;
    }

    private static List<Integer> medianPrimeList(PrimeDp dp) {
        BigInteger total = dp.suffixCount[0][dp.target];
        if (total.equals(BigInteger.ZERO)) {
            throw new IllegalArgumentException("there is no prime list for the requested target");
        }
        return kthPrimeList(dp, total.add(BigInteger.ONE).divide(BigInteger.TWO));
    }

    private static long productMod(List<Integer> values) {
        long product = 1;
        for (int value : values) {
            product = product * value % MOD;
        }
        return product;
    }

    private static void enumerateBruteforce(
            List<Integer> primes,
            int start,
            int remaining,
            List<Integer> current,
            List<List<Integer>> lists) {
        if (remaining == 0) {
            lists.add(new ArrayList<>(current));
            return;
        }

        for (int i = start; i < primes.size(); ++i) {
            int prime = primes.get(i);
            if (prime > remaining) {
                break;
            }
            current.add(prime);
            enumerateBruteforce(primes, i + 1, remaining - prime, current, lists);
            current.remove(current.size() - 1);
        }
    }

    private static List<List<Integer>> bruteLists(int target) {
        List<List<Integer>> lists = new ArrayList<>();
        enumerateBruteforce(primesUpTo(target), 0, target, new ArrayList<>(), lists);
        return lists;
    }

    private static void requireCheckpoint(boolean ok, String message) {
        if (!ok) {
            throw new AssertionError("checkpoint failed: " + message);
        }
    }

    private static void runCheckpoints() {
        PrimeDp dp20 = buildDp(20);
        List<List<Integer>> expected = List.of(
                List.of(2, 5, 13),
                List.of(2, 7, 11),
                List.of(3, 17),
                List.of(7, 13));
        requireCheckpoint(bruteLists(20).equals(expected), "lexicographic lists for 20");
        requireCheckpoint(dp20.suffixCount[0][20].equals(BigInteger.valueOf(4)), "count for 20");
        requireCheckpoint(medianPrimeList(dp20).equals(List.of(2, 7, 11)), "median list for 20");
        requireCheckpoint(productMod(medianPrimeList(dp20)) == 154, "product for 20");

        for (int target = 2; target <= 60; ++target) {
            PrimeDp dp = buildDp(target);
            List<List<Integer>> lists = bruteLists(target);
            requireCheckpoint(dp.suffixCount[0][target].equals(BigInteger.valueOf(lists.size())),
                    "DP count matches brute force for " + target);

            if (!lists.isEmpty()) {
                requireCheckpoint(medianPrimeList(dp).equals(lists.get((lists.size() - 1) / 2)),
                        "median matches brute force for " + target);
                requireCheckpoint(kthPrimeList(dp, BigInteger.ONE).equals(lists.get(0)),
                        "first rank for " + target);
                requireCheckpoint(kthPrimeList(dp, BigInteger.valueOf((lists.size() + 1L) / 2))
                                .equals(lists.get((lists.size() - 1) / 2)),
                        "middle rank for " + target);
                requireCheckpoint(kthPrimeList(dp, BigInteger.valueOf(lists.size())).equals(lists.get(lists.size() - 1)),
                        "last rank for " + target);
            }
        }
    }

    private static Options parseArguments(String[] args) {
        Options options = new Options();
        for (String arg : args) {
            if (arg.equals("--skip-checkpoints")) {
                options.runCheckpoints = false;
                continue;
            }
            if (arg.startsWith("-")) {
                throw new IllegalArgumentException("unknown option: " + arg);
            }
            options.target = Integer.parseInt(arg);
        }

        if (options.target < 0) {
            throw new IllegalArgumentException("target must be nonnegative");
        }
        return options;
    }

    public static void main(String[] args) {
        Options options = parseArguments(args);
        if (options.runCheckpoints) {
            runCheckpoints();
        }

        PrimeDp dp = buildDp(options.target);
        System.out.printf("%09d%n", productMod(medianPrimeList(dp)));
    }
}