Day 1, Task 2: The Primes

Precomputation Generate all 5-digit primes via the Sieve of Eratosthenes (10000 to 99999). There are 8713 such primes. Filter to those with digit sum S. Typically 100 -- 400 remain. Build a prefix set: for each length...

Updated May 21, 2026

Track IOI

Year 1993

Statement Rendered from TeX

TeXC++Rendered statement

Problem statement

Problem Statement

Rendered from the "Problem Statement" section in the LaTeX write-up.

Open TeX section

Fill a $5 \times 5$ grid with digits such that:

Each row (read left-to-right) is a 5-digit prime.
Each column (read top-to-bottom) is a 5-digit prime.
The main diagonal (top-left to bottom-right) is a 5-digit prime.
The anti-diagonal (top-right to bottom-left) is a 5-digit prime.
Every row has the same digit sum $S$.
The top-left digit equals a given digit $d$.
Output all valid grids in lexicographic order.

Editorial

The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.

Raw TeX

Solution

Precomputation

Generate all 5-digit primes via the Sieve of Eratosthenes ($10000$ to $99999$). There are $8713$ such primes.
Filter to those with digit sum $S$. Typically $100$--$400$ remain.
Build a prefix set: for each length $\ell \in \{1, 2, 3, 4, 5\}$, store the set of all $\ell$-digit prefixes of primes with digit sum $S$.

Row-by-Row Backtracking with Prefix Pruning

Fill the grid row by row (rows 0 through 4). For each candidate row (a prime with digit sum $S$):

Row 0: Must start with digit $d$.
\textbf{After placing row $k$:} Check that all 5 column prefixes of length $k+1$ are in the prefix set. Also check both diagonal prefixes of length $k+1$.
Row 4: After placement, all columns and diagonals are fully determined. The prefix check at length 5 is equivalent to verifying they are primes with digit sum $S$.
This aggressive pruning eliminates the vast majority of candidates early.

Complexity Analysis

Let $P_S$ denote the number of 5-digit primes with digit sum $S$ (typically $100$--$400$).
In the worst case without pruning, there are $P_S^5$ combinations. With prefix pruning, the effective search tree is orders of magnitude smaller.
Space: $O(P)$ where $P$ is the number of 5-digit primes, plus $O(1)$ for the $5 \times 5$ grid.

Notes

Prefix pruning is the critical optimization. After placing row $k$, each column has a $(k{+}1)$-digit prefix that must extend to a valid 5-digit prime. Most candidates fail this check, dramatically reducing the search tree.
The prefix sets are built during precomputation from all primes with the required digit sum, so they automatically enforce both the primality and digit-sum constraints on columns and diagonals.
Solutions are output in lexicographic order, separated by blank lines.

C++

Clean code view with a raw-file link when you want the original source.

Raw file

// IOI 1993 - Day 1, Task 2: The Primes
// Fill a 5x5 grid so each row, column, and both diagonals are 5-digit primes,
// all rows have the same digit sum S, and grid[0][0] = given digit.
// Backtracking with prefix pruning on columns and diagonals.
#include <bits/stdc++.h>
using namespace std;

bool sieve[100000];
int S, startDigit;
int grid[5][5];
vector<string> solutions;

// Primes with digit sum S, stored as digit arrays
vector<vector<int>> candidates;

// Valid prefixes of length 1..5 among primes with digit sum S
set<int> validPrefixes[6];

int digitSum(int p) {
    int s = 0;
    while (p) { s += p % 10; p /= 10; }
    return s;
}

bool checkPartialCols(int rowsFilled) {
    for (int c = 0; c < 5; c++) {
        int prefix = 0;
        for (int r = 0; r < rowsFilled; r++)
            prefix = prefix * 10 + grid[r][c];
        if (!validPrefixes[rowsFilled].count(prefix))
            return false;
    }
    return true;
}

bool checkPartialDiags(int rowsFilled) {
    // Main diagonal
    int prefix = 0;
    for (int i = 0; i < rowsFilled; i++)
        prefix = prefix * 10 + grid[i][i];
    if (!validPrefixes[rowsFilled].count(prefix))
        return false;

    // Anti-diagonal
    prefix = 0;
    for (int i = 0; i < rowsFilled; i++)
        prefix = prefix * 10 + grid[i][4 - i];
    if (!validPrefixes[rowsFilled].count(prefix))
        return false;

    return true;
}

void solve(int row) {
    if (row == 5) {
        string sol;
        for (int r = 0; r < 5; r++) {
            for (int c = 0; c < 5; c++)
                sol += (char)('0' + grid[r][c]);
            sol += '\n';
        }
        solutions.push_back(sol);
        return;
    }

    for (auto& d : candidates) {
        if (row == 0 && d[0] != startDigit) continue;

        for (int c = 0; c < 5; c++) grid[row][c] = d[c];

        if (!checkPartialCols(row + 1)) continue;
        if (!checkPartialDiags(row + 1)) continue;

        solve(row + 1);
    }
}

int main() {
    // Sieve of Eratosthenes
    memset(sieve, true, sizeof(sieve));
    sieve[0] = sieve[1] = false;
    for (int i = 2; i < 100000; i++)
        if (sieve[i])
            for (long long j = (long long)i * i; j < 100000; j += i)
                sieve[j] = false;

    scanf("%d%d", &S, &startDigit);

    // Build candidate list and prefix sets
    for (int p = 10000; p <= 99999; p++) {
        if (!sieve[p] || digitSum(p) != S) continue;
        vector<int> d(5);
        int tmp = p;
        for (int i = 4; i >= 0; i--) { d[i] = tmp % 10; tmp /= 10; }
        candidates.push_back(d);

        int prefix = 0;
        for (int len = 1; len <= 5; len++) {
            prefix = prefix * 10 + d[len - 1];
            validPrefixes[len].insert(prefix);
        }
    }

    solve(0);

    if (solutions.empty()) {
        printf("NONE\n");
    } else {
        sort(solutions.begin(), solutions.end());
        for (int i = 0; i < (int)solutions.size(); i++) {
            if (i > 0) printf("\n");
            printf("%s", solutions[i].c_str());
        }
    }
    return 0;
}

Show raw files

TeX write-upcompetitive_programming/ioi/1993/the_primes/solution.texC++ implementationcompetitive_programming/ioi/1993/the_primes/solution.cpp