Prime Number Program in Python: Primes in a Range

A prime number program tests whether you understand why the divisor loop stops at the square root, not just whether you can write one.

This article covers three Python implementations with increasing efficiency: trial division, the 6k±1 optimisation, and the Sieve of Eratosthenes for range queries. Every algorithm is traced manually so the numbers are verifiable, not just plausible.

What makes a number prime

A prime number is a positive integer greater than 1 that has exactly two factors: 1 and itself. The smallest prime is 2, which is also the only even prime; every other even number is divisible by 2, giving it a third factor.

Key edge cases that all three algorithms must handle:

• 1 is not prime. It has only one factor (itself), not two.
• 2 is prime. It is the only even prime.
• Negative numbers and 0 are not prime by the standard definition.

The first ten primes in order: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29.

A composite number is any positive integer greater than 1 that is not prime. The number 35 is composite because 35 = 5 × 7.

Trial division: basic prime check

Trial division checks whether any integer from 2 up to the square root of n divides n without a remainder. The square root bound works because if n has a factor larger than √n, it must have a paired factor smaller than √n, so checking up to √n is sufficient.

Python uses int(n ** 0.5) to compute the integer part of the square root. The Python standard library also provides math.isqrt(n) for integer square roots from Python 3.8 onward, which avoids float precision edge cases on large inputs.

def is_prime(n):
    if n < 2:
        return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def primes_in_range_trial(start, end):
    return [n for n in range(start, end + 1) if is_prime(n)]

# Example
print(primes_in_range_trial(10, 50))
# Output: [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Manual trace for n = 29 (prime):

• int(29 ** 0.5) + 1 = 6, so the loop runs i = 2, 3, 4, 5
• i=2: 29 % 2 = 1 (not zero, continue)
• i=3: 29 % 3 = 2 (not zero, continue)
• i=4: 29 % 4 = 1 (not zero, continue)
• i=5: 29 % 5 = 4 (not zero, continue)
• Loop ends without a hit. Return True. Correct: 29 is prime.

Manual trace for n = 35 (composite):

• int(35 ** 0.5) + 1 = 6, loop runs i = 2, 3, 4, 5
• i=2: 35 % 2 = 1 (continue)
• i=3: 35 % 3 = 2 (continue)
• i=4: 35 % 4 = 3 (continue)
• i=5: 35 % 5 = 0 → return False. Correct: 35 = 5 × 7.

Time complexity: O(√n) per number, so O(n√n) for a range of n numbers. Fine for small ranges but slow for ranges in the hundreds of thousands.

The digit-extraction loop pattern here shares structure with Armstrong number checks, where the algorithm also loops over numeric properties of a number to reach a yes/no conclusion.

The 6k±1 optimisation

The trial division loop tests every integer from 2 to √n, including composites like 4, 6, 8, 9, and 10 that can never divide a prime. The 6k±1 rule eliminates those upfront.

The logic: every integer can be written as one of 6k, 6k+1, 6k+2, 6k+3, 6k+4, or 6k+5. Of those six forms:

• 6k, 6k+2, 6k+4 are divisible by 2
• 6k and 6k+3 are divisible by 3

That leaves only 6k+1 and 6k+5 (equivalently 6k−1) as possible prime positions. After ruling out 2 and 3 explicitly, the loop tests only divisors of those two forms.

def is_prime_fast(n):
    if n < 2:
        return False
    if n == 2 or n == 3:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    k = 5
    while k * k <= n:
        if n % k == 0 or n % (k + 2) == 0:
            return False
        k += 6
    return True

def primes_in_range_fast(start, end):
    return [n for n in range(start, end + 1) if is_prime_fast(n)]

Manual trace for n = 37 (prime):

• Not < 2. Not 2 or 3. 37 is odd, so 37 % 2 != 0. 36 is divisible by 3, but 37 is not, so 37 % 3 != 0.
• k=5: k*k = 25, which is <= 37. Check 37 % 5 = 2 (not 0). Check 37 % 7 = 2 (not 0).
• k=11: k*k = 121, which is > 37. Loop ends.
• Return True. Correct: 37 is prime.

Manual trace for n = 49 (composite):

• 49 is odd (49 % 2 = 1). 48 is divisible by 3, but 49 is not.
• k=5: k*k = 25, which is <= 49. Check 49 % 5 = 4 (not 0). Check 49 % 7 = 0 → return False.
• Correct: 49 = 7 × 7.

The loop step is 6, so divisor candidates are 5, 11, 17, 23, 29 (the 6k−1 series) and 7, 13, 19, 25, 31 (the 6k+1 series). Not every candidate in those series is prime: 5² = 25 is composite, but the k=5 iteration would catch it before the k=11 step anyway. The missed composites are rare and the algorithm still returns the correct result.

Sieve of Eratosthenes: all primes in a range

When you need every prime in a range rather than a single check, the Sieve of Eratosthenes is the standard approach. Instead of testing each number individually, it marks all multiples of each prime as composite in a single pass over a Boolean list.

def primes_in_range_sieve(start, end):
    if end < 2:
        return []
    sieve = [True] * (end + 1)
    sieve[0] = sieve[1] = False
    p = 2
    while p * p <= end:
        if sieve[p]:
            for i in range(p * p, end + 1, p):
                sieve[i] = False
        p += 1
    return [i for i in range(max(2, start), end + 1) if sieve[i]]

# Example
print(primes_in_range_sieve(10, 50))
# Output: [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Manual trace for end = 20:

Start: sieve = [T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T, T] (indices 0..20)

• Set index 0 and 1 to False.
• p=2: p*p = 4, which is <= 20. Mark 4, 6, 8, 10, 12, 14, 16, 18, 20 as False.
• p=3: p*p = 9, which is <= 20. Mark 9 and 15 as False (12 and 18 already False).
• p=4: sieve[4] = False, skip.
• p=5: p*p = 25, which is > 20. Loop ends.

Indices still True: 2, 3, 5, 7, 11, 13, 17, 19. These eight numbers are all primes up to 20, verified against the manual trace above.

Why start marking from p * p and not from p + p? All composites smaller than p² have already been marked by a smaller prime. Starting from p² avoids redundant work; this is the key inner optimisation of the Sieve.

For general list-traversal patterns with Boolean arrays, the approach is structurally similar to the range-sum technique in Python array programs: allocate a container, update it in a single pass, collect results at the end. The Python programs practice collection has additional range-based exercises that follow the same pattern.

Choosing the right algorithm for placement rounds

Algorithm	Time (single number)	Time (range 2..n)	Space	Best use
Trial division	O(√n)	O(n√n)	O(1)	Single primality check
6k±1	O(√n / 3)	O(n√n / 3)	O(1)	Single check with tighter constant
Sieve of Eratosthenes	N/A	O(n log log n)	O(n)	All primes up to n

For placement coding questions:

• If the question asks to check whether a given number is prime, 6k±1 is the cleanest choice.
• If the question asks to print or count all primes in a range, the Sieve is the expected answer at the SP/Digital level.
• Trial division is acceptable in NQT-level questions but will cost marks on efficiency when the Sieve is the expected answer.

The jump from trial division to the Sieve is a concrete example of algorithm design thinking: same output, but a fundamentally different strategy. Trial division asks “is this number prime?” once per candidate in the range. The Sieve asks a different question entirely: which numbers survive after removing all composites? That reframing produces an algorithm with much better scaling. The same instinct for eliminating redundant work applies in AI engineering, where repeated model inference calls are expensive in the same way individual primality tests are expensive on a range of ten million numbers. If you want to experiment with that pattern applied to LLM API calls, TinkerLLM at ₹299 is a live Python sandbox where you can run equivalent before/after experiments with real AI APIs.