Find Prime Numbers in a Given Range: C, C++, Java, and Python

Finding all prime numbers in a given range is a standard warm-up problem in AMCAT Automata, CoCubes, and most campus-placement coding rounds.

The problem looks simple: loop from the lower bound to the upper bound, test each number, print the primes. The boundary condition on the primality test and the handling of edge cases 1, 2, and perfect squares like 9 and 25 are where submissions go wrong.

The Problem Setup

Given two integers low and high, print every prime number in the inclusive range [low, high].

Most online judges use inclusive bounds. If the problem says “excluding the bounds,” adjust the loop to start at low + 1 and stop before high. Read the specification before coding.

Four values every implementation must handle correctly:

Input n	Prime?	Reason
1	No	Only one distinct factor; two are required
2	Yes	The only even prime
9	No	9 = 3 × 3; the i * i <= n boundary catches it
25	No	25 = 5 × 5; same boundary catches it

The boundary matters. Using i * i < n instead of i * i <= n misclassifies perfect squares of primes: for n = 9, the test 3 * 3 < 9 is false so the loop exits without testing i = 3, and 9 is wrongly marked prime. The <= form is correct.

Building the is_prime Helper

All four implementations share one primality helper. The logic, in order:

• Return false for any n below 2. Neither 0 nor 1 qualifies as prime by definition.
• Return true for n = 2. This is the only even prime; the next check would incorrectly reject it.
• Return false for any even n above 2. Every even number above 2 has 2 as a factor.
• Loop from i = 3 to sqrt(n), stepping by 2. If any value of i divides n exactly, return false. If the loop completes without a match, return true.

The odd-step skip cuts iterations roughly in half. After confirming that n is itself odd (the third check), only odd divisors need testing; an even divisor cannot divide an odd number.

The i * i <= n boundary works because if n has a factor f larger than sqrt(n), its paired factor n/f must be smaller than sqrt(n). No composite number hides all its factors above sqrt(n), so checking up to sqrt(n) is sufficient.

The function-based pattern used here (a dedicated boolean function with early returns, called inside a range loop) is the same structure as the string palindrome check: isolate the test logic in one function, keep the caller clean.

C and C++ Programs for a Range

C

#include <stdio.h>

int is_prime(int n) {
    if (n < 2) return 0;
    if (n == 2) return 1;
    if (n % 2 == 0) return 0;
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return 0;
    }
    return 1;
}

int main() {
    int low, high;
    printf("Enter lower bound: ");
    scanf("%d", &low);
    printf("Enter upper bound: ");
    scanf("%d", &high);
    printf("Primes between %d and %d:\n", low, high);
    for (int n = low; n <= high; n++) {
        if (is_prime(n))
            printf("%d ", n);
    }
    printf("\n");
    return 0;
}

Sample run for low = 10, high = 30: 11 13 17 19 23 29

No <math.h> is needed here. The i * i <= n test uses integer multiplication only, so there are no floating-point precision concerns about perfect squares.

C++

#include <iostream>
using namespace std;

bool is_prime(int n) {
    if (n < 2) return false;
    if (n == 2) return true;
    if (n % 2 == 0) return false;
    for (int i = 3; i * i <= n; i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

int main() {
    int low, high;
    cout << "Enter lower bound: ";
    cin >> low;
    cout << "Enter upper bound: ";
    cin >> high;
    cout << "Primes between " << low << " and " << high << ":\n";
    for (int n = low; n <= high; n++) {
        if (is_prime(n))
            cout << n << " ";
    }
    cout << "\n";
    return 0;
}

The C++ version drops <cmath> entirely and uses the same i * i <= n integer boundary. The bool return type is cleaner than C’s int-as-boolean, but the underlying logic is identical. Both versions run in O(m × sqrt(high)) time, where m is the count of candidates in the range.

Java and Python Programs for a Range

Java

import java.util.Scanner;

public class PrimesInRange {

    static boolean isPrime(int n) {
        if (n < 2) return false;
        if (n == 2) return true;
        if (n % 2 == 0) return false;
        for (int i = 3; i * i <= n; i += 2) {
            if (n % i == 0) return false;
        }
        return true;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter lower bound: ");
        int low = sc.nextInt();
        System.out.print("Enter upper bound: ");
        int high = sc.nextInt();
        System.out.println("Primes between " + low + " and " + high + ":");
        for (int n = low; n <= high; n++) {
            if (isPrime(n))
                System.out.print(n + " ");
        }
        System.out.println();
        sc.close();
    }
}

isPrime is declared static so main() calls it without creating an object instance. sc.close() prevents resource-leak warnings in static analysis tools and online judge environments that check for it.

Python

def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False
        i += 2
    return True

def primes_in_range(low, high):
    return [n for n in range(low, high + 1) if is_prime(n)]

if __name__ == "__main__":
    low = int(input("Enter lower bound: "))
    high = int(input("Enter upper bound: "))
    result = primes_in_range(low, high)
    print("Primes between", low, "and", high)
    print(" ".join(map(str, result)))

Sample run for low = 2, high = 20: 2 3 5 7 11 13 17 19

The list comprehension in primes_in_range is idiomatic Python and reads exactly like the problem statement. The __main__ guard keeps the two functions importable as a module without triggering input prompts.

Sieve of Eratosthenes for Large Ranges

The trial-division approach calls is_prime once per candidate, each call taking O(sqrt(n)) time. For a large range with many candidates, this adds up. The Sieve of Eratosthenes eliminates repeated work by marking all composites in a single pass, running in O(high × log(log(high))) time overall.

def sieve_primes_in_range(low, high):
    if high < 2:
        return []
    sieve = [True] * (high + 1)
    sieve[0] = sieve[1] = False
    i = 2
    while i * i <= high:
        if sieve[i]:
            for j in range(i * i, high + 1, i):
                sieve[j] = False
        i += 1
    return [n for n in range(max(low, 2), high + 1) if sieve[n]]

Two correctness details:

• The inner loop starts at i * i, not 2 * i. Multiples of i smaller than i * i have already been marked composite by earlier primes in the outer loop. Starting at 2 * i is correct but slower.
• Indices 0 and 1 are explicitly set to False before the loop. The sieve marks composites but does not automatically exclude values below 2.

Trace through sieve for range 2 to 20:

• i = 2: mark 4, 6, 8, 10, 12, 14, 16, 18, 20 as composite
• i = 3: sieve[3] is still True; mark 9, 12, 15, 18 as composite
• i = 4: sieve[4] is already False — skip
• i = 5: 5 * 5 = 25 exceeds 20 — outer loop ends

Result: 2, 3, 5, 7, 11, 13, 17, 19

When to use each approach:

Range size	Approach	Why
Up to 10,000	Trial division	Simple; fast enough for any modern machine
Up to 10^6	Either	Sieve starts gaining a meaningful speed advantage
Above 10^6	Sieve	Trial division exceeds typical 1-second online-judge limits

Where This Problem Appears in Placement Tests

Three common question formats in service-tier placement rounds:

• Print all primes in [N1, N2]: The direct format. Any boundary or edge-case error fails the automated judge immediately.
• Sum of primes in a range: Accumulate instead of printing. Summing all primes strictly between 7 and 24 (exclusive bounds) gives 83 — primes 11, 13, 17, 19, and 23.
• Count of primes in a range: Count rather than print. Appears in AMCAT Automata and several HackerRank company assessments.

Getting the range problem correct in under 10 minutes leaves time for the harder problems in the same session. The find smallest and largest element in an array is another warm-up at the same difficulty level, where the boundary initialisation (not the algorithm itself) decides whether the submission passes. For the layer above these warm-ups, data structures interview questions covers the problems that separate shortlisted candidates from the pack.

The boundary-condition discipline from this article (choosing i * i <= n over i * i < n, starting the sieve from i * i rather than 2 * i) is the same kind of precision that shows up in AI systems. Context window limits, tokeniser rules, and attention mask boundaries all follow the same principle: process exactly the range you need, no more. TinkerLLM at ₹299 is where that reasoning transfers from primality checks to hands-on AI work.