Kotlin: The Last Prime Number in a Range

Walk the range backwards. For each candidate, run a primality test. Return the first match. The series finale that combines two earlier episodes.

The last episode of this series. Combines episode 18's prime test with episode 9's range-iteration to find the largest prime in a given window.

The Copilot prompt

// Find the largest prime number in a range, or null if none exist
fun lastPrimeInRange(start: Int, end: Int): Int? {

Copilot generates:

fun isPrime(n: Int): Boolean {
  if (n < 2) return false
  for (i in 2..Math.sqrt(n.toDouble()).toInt()) {
    if (n % i == 0) return false
  }
  return true
}

fun lastPrimeInRange(start: Int, end: Int): Int? {
  for (num in end downTo start) {
    if (isPrime(num)) return num
  }
  return null
}

fun main() {
  val start = 0
  val end = 10
  val lastPrime = lastPrimeInRange(start, end)
  println("Last prime in $start..$end: $lastPrime")   // 7
}

Walkthrough

1. isPrime(n). Trial division up to √n. Same as episode 18's extension function, but as a free function.

2. for (num in end downTo start). Walks backwards from end to start. The first prime found is the largest.

3. return num on first match. Short-circuit. We don't need to check the rest.

4. return null if no match. Empty result for ranges with no primes (e.g., 0..1).

Why backwards

To find the largest, walk from the top. The first match is the answer.

If we walked forward, we'd have to track the largest seen so far:

fun lastPrimeForward(start: Int, end: Int): Int? {
  var last: Int? = null
  for (num in start..end) {
    if (isPrime(num)) last = num
  }
  return last
}

Works, but always iterates the full range. The backwards version typically stops early.

Using Kotlin idioms

fun lastPrimeInRange(start: Int, end: Int): Int? =
  (end downTo start).firstOrNull { isPrime(it) }

firstOrNull(predicate) walks the iterable, returns the first match (or null). One line, same behavior, no manual loop.

(end downTo start) is an IntProgression — same as a regular range but in descending order.

Performance

For a range like 0..1000, lastPrimeInRange checks ~1-3 numbers before finding 997 (the largest prime under 1000). Fast.

For a range like 100_000_000..100_001_000, primality test is O(√n) ≈ 10,000 iterations per candidate. Worst case (no primes in range) is 1000 × 10,000 = 10M operations. Still sub-second.

For huge ranges, the Sieve of Eratosthenes precomputes all primes up to n in O(n log log n) — trade memory for speed if you'll do many such queries.

Generalising: nth-largest prime

fun nthLargestPrimeInRange(start: Int, end: Int, n: Int): Int? =
  (end downTo start).asSequence()
    .filter { isPrime(it) }
    .drop(n - 1)
    .firstOrNull()

asSequence() makes it lazy. filter keeps primes. drop(n - 1) skips the first n-1; firstOrNull() takes the next.

For "5th largest prime under 100": nthLargestPrimeInRange(0, 100, 5) → 79.

All primes in a range

fun primesInRange(start: Int, end: Int): List<Int> =
  (start..end).filter { isPrime(it) }

filter returns all matching values. For 1..100: [2, 3, 5, 7, ..., 97].

Edge cases

• Empty range (start > end). (end downTo start) is empty; returns null.
• Range with no primes (0..1). Returns null.
• Negative numbers. isPrime(-5) returns false (handled by n < 2). Negatives never count as primes.
• Huge numbers. Trial division dies past ~10^15. Use Miller-Rabin or BigInteger's isProbablePrime for cryptographic-size primes.

Probabilistic test for big primes

import java.math.BigInteger

fun isProbablyPrime(n: BigInteger, certainty: Int = 20): Boolean {
  return n.isProbablePrime(certainty)
}

println(isProbablyPrime(BigInteger("479001599")))   // true (12!-1, is prime)

BigInteger.isProbablePrime(certainty) uses Miller-Rabin under the hood. For certainty = 20, the probability of a false positive is < 1 in a million.

For real primality testing of huge numbers (e.g., RSA key generation), this is the standard.

Recap of the series

Across 40 episodes, this series covered Copilot's behaviour on small Kotlin (and one Swift, one Python) puzzles:

• Lists and arrays — filter, count, max, partition, joinToString.
• Strings — capitalize, format, parse.
• Dates — LocalDate.parse, Period.between, dayOfWeek, leap years, lengthOfMonth.
• Functions — first-class lambdas, higher-order, closures, function references.
• Compose UI — buttons, text fields, ViewModel, mutableStateOf, mutableStateListOf.
• Networking — Ktor + kotlinx.serialization.
• Persistence — Firestore.
• OOP — classes, methods, data class, extension functions.
• Algorithms — two-sum, primality, age calculation.

Common Copilot lesson: the comment is the spec. Vague prompts produce vague code; precise prompts produce focused code. Naming the API (LocalDate, replaceFirstChar, mutableStateOf) steers Copilot to the right idiom.

Common mistakes (whole series)

• Hardcoding strings that should come from getDisplayName(...). Locale-aware code wins long-term.
• SimpleDateFormat instead of DateTimeFormatter. Modern API is thread-safe, immutable, type-rich.
• Mutating where copying is correct. Functional style avoids whole categories of bugs.
• Skipping remember in Composables. Causes infinite recomposition or lost state.
• Trusting Copilot's first suggestion. It's a starting point. Always read, always test.

Recap

(end downTo start).firstOrNull { isPrime(it) } for the largest prime. Backwards iteration short-circuits. For huge primes, use BigInteger.isProbablePrime(certainty) instead of trial division. For "all primes in range," (start..end).filter { isPrime(it) }. The general lesson from the series: Copilot reads comments as specs — write precise comments, get precise code.

Series complete. Use Copilot as a productivity tool, not a substitute for understanding.