Learn how to check if a number is prime and find all prime numbers up to N in Python.

Find Prime Numbers

Problem

A prime number is a number greater than 1 that has no divisors other than 1 and itself.

2, 3, 5, 7, 11, 13, 17, 19, 23, 29 ...

Two problems to solve:

Part 1 — check if a single number is prime:

Input:  7
Output: True

Input:  10
Output: False

Input:  1
Output: False

Input:  2
Output: True

Part 2 — find all prime numbers up to N:

Input:  30
Output: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

Logic

Part 1 — is a number prime?

Numbers less than 2 are never prime
Check if any number from 2 to √n divides n evenly
If any divisor found — not prime
If no divisor found — prime

Why only up to √n? If n has a factor larger than √n, it must also have a factor smaller than √n. So we only need to check up to √n.

Example: n = 36
√36 = 6
Factors of 36: 1×36, 2×18, 3×12, 4×9, 6×6
Every factor above 6 pairs with one below 6
So checking up to 6 is enough

Part 2 — Sieve of Eratosthenes:

Create a list of True for every number from 0 to N
Start at 2 — mark all multiples of 2 as False (not prime)
Move to 3 — mark all multiples of 3 as False
Skip numbers already marked False
Continue until √N
All positions still True are prime

Part 1 — Solution 1: basic loop

Check every number from 2 to n-1. Simple but slow for large numbers.

def is_prime(n):
    # numbers less than 2 are not prime
    if n < 2:
        return False

    # check every number from 2 up to n-1
    for i in range(2, n):
        if n % i == 0:
            return False   # found a divisor — not prime

    return True   # no divisor found — prime


print(is_prime(2))    # True
print(is_prime(7))    # True
print(is_prime(10))   # False
print(is_prime(1))    # False
print(is_prime(97))   # True

Code Execution — Part 1 Solution 1

Trace through is_prime(7):

range(2, 7) = 2, 3, 4, 5, 6

`i`	`7 % i`	`== 0?`
`2`	`1`	No
`3`	`1`	No
`4`	`3`	No
`5`	`2`	No
`6`	`1`	No

No divisor found → True

Trace through is_prime(10):

`i`	`10 % i`	`== 0?`
`2`	`0`	Yes → return `False` immediately

Part 1 — Solution 2: optimized with square root

Only check up to √n — much faster for large numbers.

import math

def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True    # 2 is prime
    if n % 2 == 0:
        return False   # even numbers > 2 are not prime

    # only check odd numbers from 3 up to √n
    # step of 2 skips even numbers — they cannot be prime
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False   # found a divisor — not prime

    return True


print(is_prime(2))     # True
print(is_prime(7))     # True
print(is_prime(10))    # False
print(is_prime(97))    # True
print(is_prime(100))   # False

Code Execution — Part 1 Solution 2

Trace through is_prime(97):

√97 ≈ 9.85 → check up to 9

range(3, 10, 2) = 3, 5, 7, 9

`i`	`97 % i`	`== 0?`
`3`	`1`	No
`5`	`2`	No
`7`	`6`	No
`9`	`7`	No

No divisor found → True

Trace through is_prime(100):

100 % 2 == 0 → immediately return False

Checking only up to √n dramatically reduces the work. For n = 1,000,000:

Solution 1 checks up to 999,999 numbers
Solution 2 checks up to only 500 numbers

That is a 2,000x speedup.

Part 2 — Solution 1: brute force

Use is_prime() on every number from 2 to N.

import math

def is_prime(n):
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    for i in range(3, int(math.sqrt(n)) + 1, 2):
        if n % i == 0:
            return False
    return True

def primes_up_to(n):
    return [num for num in range(2, n + 1) if is_prime(num)]


print(primes_up_to(30))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

print(primes_up_to(50))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

Code Execution — Part 2 Solution 1

Trace through primes_up_to(15):

Check each number from 2 to 15:

`num`	`is_prime(num)`	Added?
`2`	True	✅
`3`	True	✅
`4`	False (4 % 2 = 0)	❌
`5`	True	✅
`6`	False (6 % 2 = 0)	❌
`7`	True	✅
`8`	False	❌
`9`	False (9 % 3 = 0)	❌
`10`	False	❌
`11`	True	✅
`12`	False	❌
`13`	True	✅
`14`	False	❌
`15`	False (15 % 3 = 0)	❌

Result: [2, 3, 5, 7, 11, 13]

Part 2 — Solution 2: Sieve of Eratosthenes

The most efficient algorithm for finding all primes up to N. Instead of checking each number independently, it eliminates multiples of each prime.

def sieve_of_eratosthenes(n):
    if n < 2:
        return []

    # create a list — index represents the number
    # True means "still possibly prime"
    # start everything as True
    is_prime = [True] * (n + 1)

    # 0 and 1 are not prime
    is_prime[0] = False
    is_prime[1] = False

    # start at 2 — the first prime
    # only go up to √n
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:   # only process if still marked prime
            # mark all multiples of i as not prime
            # start at i*i — smaller multiples already marked
            for multiple in range(i * i, n + 1, i):
                is_prime[multiple] = False

    # collect all indexes still marked True
    return [num for num, prime in enumerate(is_prime) if prime]


print(sieve_of_eratosthenes(30))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

print(sieve_of_eratosthenes(50))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

print(len(sieve_of_eratosthenes(1000)))
# 168 — there are 168 primes below 1000

Code Execution — Sieve

Trace through sieve_of_eratosthenes(20):

Initial state:

Index: 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
Value: F  F  T  T  T  T  T  T  T  T   T  T  T  T  T  T  T  T  T  T  T

(0 and 1 set to False)

i = 2 — mark multiples of 2 starting from 4 (2×2): Mark: 4, 6, 8, 10, 12, 14, 16, 18, 20

Index: 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
Value: F  F  T  T  F  T  F  T  F  T   F  T  F  T  F  T  F  T  F  T  F

i = 3 — mark multiples of 3 starting from 9 (3×3): Mark: 9, 12, 15, 18 (already marked some)

Index: 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16 17 18 19 20
Value: F  F  T  T  F  T  F  T  F  F   F  T  F  T  F  F  F  T  F  T  F

i = 4 — is_prime[4] is False — skip

√20 ≈ 4.47 — stop here

Collect all True indexes: [2, 3, 5, 7, 11, 13, 17, 19]

Why start marking from i * i instead of i * 2?

All smaller multiples of i were already marked by earlier primes. For example, when i = 5, multiples 5×2=10 and 5×3=15 were already marked by 2 and 3. The first unmarked multiple is 5×5=25. Starting from i*i avoids redundant work.

Part 2 — Solution 3: using a generator

Generate prime numbers lazily — one at a time on demand.

def prime_generator(limit):
    """Yields prime numbers up to limit one at a time."""
    for num in range(2, limit + 1):
        # check if num is divisible by any smaller number
        is_prime = all(num % i != 0 for i in range(2, int(num ** 0.5) + 1))
        if is_prime:
            yield num


# collect all primes up to 30
primes = list(prime_generator(30))
print(primes)
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

# use in a for loop — memory efficient
for prime in prime_generator(50):
    print(prime, end=" ")
# 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Code Execution — Solution 3

Trace through first 3 yields of prime_generator(10):

num = 2: range(2, 2) is empty → all(...) on empty = True → yield 2

num = 3: range(2, 2) is empty (√3 ≈ 1.7, int = 1) → True → yield 3

num = 4: range(2, 3) = [2] 4 % 2 == 0 → all(...) = False → not prime, skip

num = 5: range(2, 3) = [2] 5 % 2 = 1 ≠ 0 → True → yield 5

Performance comparison

import time

n = 100000

# brute force
start = time.perf_counter()
brute = primes_up_to(n)
print(f"Brute force: {time.perf_counter() - start:.4f}s — {len(brute)} primes")

# sieve
start = time.perf_counter()
sieve = sieve_of_eratosthenes(n)
print(f"Sieve:       {time.perf_counter() - start:.4f}s — {len(sieve)} primes")

Output:

Brute force: 0.2341s — 9592 primes
Sieve:       0.0089s — 9592 primes

The sieve is about 26x faster for 100,000 numbers.

Which solution to use?

Solution	How	Best when
Part 1 — Solution 1	Check all up to n	Learning the concept
Part 1 — Solution 2	Check up to √n	Production code for single number
Part 2 — Solution 1	Call is_prime for each	Small ranges
Part 2 — Solution 2	Sieve of Eratosthenes	Large ranges — best performance
Part 2 — Solution 3	Generator	Memory efficient, on-demand

Output

True
True
False
False
True

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
168

Find Prime Numbers

Find Prime Numbers

Problem

Logic

Flow

Part 1 — Solution 1: basic loop

Code Execution — Part 1 Solution 1

Part 1 — Solution 2: optimized with square root

Code Execution — Part 1 Solution 2

Part 2 — Solution 1: brute force

Code Execution — Part 2 Solution 1

Part 2 — Solution 2: Sieve of Eratosthenes

Code Execution — Sieve

Part 2 — Solution 3: using a generator

Code Execution — Solution 3

Performance comparison

Which solution to use?

Output

On this page