ProblemsTemplatesA prime checked at compile time
IntermediateTemplates

A prime checked at compile time

Context

The next task in this track (the Residue ring) needs to know whether a number is prime while the program is still compiling — to forbid division for composite moduli. A normal runtime function will not do: the answer has to exist before the program runs. C++ has a keyword for functions like this.

Task

Implement isPrime(n) so the compiler can evaluate it at compile time. The tests call it inside static_assert — if your function cannot run during compilation, the build fails.

Constraints

  • isPrime must be usable in static_assert (compile-time evaluation)
  • 0 and 1 are not prime; 2 is prime
  • Works up to several million — check divisors only up to the square root, or the compile-time evaluator hits its step limit
  • No lookup tables of hardcoded primes

Before you code

  • What does constexpr on a function actually promise the compiler?
  • Why does checking divisors past the square root of n waste work?
  • What happens when a constexpr evaluation runs too many steps?

Tests

  • #1Small cases at compile time
  • #2Large values stay within the step limit
  • #3Also callable at runtime

Hints

Hint 1

If n = ab and a <= b, then aa <= n. So one divisor in [2, sqrt(n)] is enough to prove n composite.

Hint 2

Avoid floating-point sqrt in constexpr code — the loop condition d * d <= n does the same job in integers.

Editorconstexpr-is-prime.cpp
Results

Hit Submit (or ⌘/Ctrl + ↵) — test results will show up here.