Loading…

easyBasicsSometimes asked

Primes up to N

Basics · 6 min

Given n, return all prime numbers from 2 to n (inclusive) as a list.

In plain English

Test each candidate with trial division to √candidate, or use the Sieve of Eratosthenes for many queries.

Examples

Example 1

Input: n = 10
Output: [2, 3, 5, 7]
Note: Primes ≤ 10.

Example 2

Input: n = 2
Output: [2]
Note: Smallest prime.

Example 3

Input: n = 1
Output: []
Note: None ≤ 1.

Constraints

1 ≤ n ≤ 10^6

Clarifying questions1First question: Need all primes, or test one number?Explore questions

Q1.Need all primes, or test one number?
All up to n — that's why the sieve fits.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Either trial-divide each i (O(n√n)) or run the Sieve of Eratosthenes (O(n log log n)) for larger n. Collect every i that stays prime.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know the sieve and the p² optimisation, not just trial division.

Where candidates slip

Per-number trial division, or crossing out from 2p.

How to stand out

Quote the O(n log log n) bound and justify starting at p².

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Sieve of Eratosthenes

TimeO(n log log n)SpaceO(n)

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Testing each number is O(n√n) — can you do all of them together?

2Hint 2Explore hint

Mark multiples of each found prime; unmarked numbers are prime.

3Hint 3Explore hint

Why can you start crossing out at p² instead of 2p?

A · Core idea

List all primes from 2 to n. The efficient method is the Sieve of Eratosthenes: mark the multiples of each prime as composite; whatever stays unmarked is prime.

Why the sieve beats per-number testing. Trial-dividing every number is O(n√n). The sieve instead does the work once per prime, crossing out its multiples, giving O(n log log n) — near-linear. It's the right tool when you need all primes up to a bound.

Why start crossing out at p·p. Any multiple of p smaller than p² (like 2p, 3p, …) has a smaller prime factor and was already crossed out when that smaller prime was processed. Starting at p² avoids redundant work.

Edge: n < 2. No primes exist, so return an empty list. The sieve needs a boolean array of size n+1, hence O(n) space.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 10

p=2

cross 4,6,8,10

Stateprimes so far: 2

Final result[2, 3, 5, 7]

C · Code with teaching comments

solution.javaJava

Sieve of Eratosthenes — optimal

2 teaching notes

1
public java.util.List<Integer> primes(int n) {
2
    boolean[] composite = new boolean[n + 1];
3
    java.util.List<Integer> out = new java.util.ArrayList<>();
4
    for (int p = 2; p <= n; p++) {
5
        if (!composite[p]) {
6
            out.add(p);
7
            for (long m = (long) p * p; m <= n; m += p) composite[(int) m] = true;
8
        }
9
    }
10
    return out;
11
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.11 lines

D · Why it works and complexityO(n log log n) timeO(n) spaceOpen the invariant and proofExplore the proof

Naming the sieve and its near-linear complexity is the strong answer; per-number trial division is the baseline.

ComplexityO(n log log n) time, O(n) space — each prime p crosses out n/p numbers; summed over primes it's O(n log log n), with an O(n) boolean array.

E · Edge cases and pitfalls4n = 2 — [2] — smallest prime.Explore edge cases

Edge cases handled

n = 2[2] — smallest prime.
n = 1[] — none ≤ 1.

Pitfalls

Starting the inner crossing-out at 2p instead of p² (slower but still correct).
Returning primes for n < 2.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic java.util.List<Integer> primes(int n) { boolean[] composite = new boolean[n + 1]; java.util.List<Integer> out = new java.util.ArrayList<>(); for (int p = 2; p <= n; p++) { if (!composite[p]) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Starting the inner crossing-out at 2p instead of p² (slower but still correct).
Returning primes for n < 2.

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sieve of Eratosthenes

Code pattern to memorize

sieve: for p where !composite[p]: cross out p*p, p*p+p, ...

Rules to remember

1Unmarked ⟹ prime.
2Cross multiples from p².
3O(n log log n).

Use this pattern when

All primes up to a bound
Precomputing prime tables

Choose another pattern when

Just one primality check — use √n trial division

Interview takeaway

Need all primes up to n? Sieve, don't trial-divide each.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternA core fresher pattern: Sieve of Eratosthenes. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Prime Number
Single-number primality via √n trial division.
Count Primes
Coming soon
Same sieve, return the count.

Same pattern

easyBasicsSometimes asked

Primes up to N

Basics · 6 min

Given n, return all prime numbers from 2 to n (inclusive) as a list.

In plain English

Test each candidate with trial division to √candidate, or use the Sieve of Eratosthenes for many queries.

Examples

Example 1

Input: n = 10
Output: [2, 3, 5, 7]
Note: Primes ≤ 10.

Example 2

Input: n = 2
Output: [2]
Note: Smallest prime.

Example 3

Input: n = 1
Output: []
Note: None ≤ 1.

Constraints

1 ≤ n ≤ 10^6

Clarifying questions1First question: Need all primes, or test one number?Explore questions

Q1.Need all primes, or test one number?
All up to n — that's why the sieve fits.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Either trial-divide each i (O(n√n)) or run the Sieve of Eratosthenes (O(n log log n)) for larger n. Collect every i that stays prime.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you know the sieve and the p² optimisation, not just trial division.

Where candidates slip

Per-number trial division, or crossing out from 2p.

How to stand out

Quote the O(n log log n) bound and justify starting at p².

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 1 · Optimal

Sieve of Eratosthenes

TimeO(n log log n)SpaceO(n)

This is the standard, expected solution — lead with it.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Testing each number is O(n√n) — can you do all of them together?

2Hint 2Explore hint

Mark multiples of each found prime; unmarked numbers are prime.

3Hint 3Explore hint

Why can you start crossing out at p² instead of 2p?

A · Core idea

List all primes from 2 to n. The efficient method is the Sieve of Eratosthenes: mark the multiples of each prime as composite; whatever stays unmarked is prime.

Edge: n < 2. No primes exist, so return an empty list. The sieve needs a boolean array of size n+1, hence O(n) space.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 10

p=2

cross 4,6,8,10

Stateprimes so far: 2

Final result[2, 3, 5, 7]

C · Code with teaching comments

solution.javaJava

Sieve of Eratosthenes — optimal

2 teaching notes

1
public java.util.List<Integer> primes(int n) {
2
    boolean[] composite = new boolean[n + 1];
3
    java.util.List<Integer> out = new java.util.ArrayList<>();
4
    for (int p = 2; p <= n; p++) {
5
        if (!composite[p]) {
6
            out.add(p);
7
            for (long m = (long) p * p; m <= n; m += p) composite[(int) m] = true;
8
        }
9
    }
10
    return out;
11
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.11 lines

D · Why it works and complexityO(n log log n) timeO(n) spaceOpen the invariant and proofExplore the proof

Naming the sieve and its near-linear complexity is the strong answer; per-number trial division is the baseline.

ComplexityO(n log log n) time, O(n) space — each prime p crosses out n/p numbers; summed over primes it's O(n log log n), with an O(n) boolean array.

E · Edge cases and pitfalls4n = 2 — [2] — smallest prime.Explore edge cases

Edge cases handled

n = 2[2] — smallest prime.
n = 1[] — none ≤ 1.

Pitfalls

Starting the inner crossing-out at 2p instead of p² (slower but still correct).
Returning primes for n < 2.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Starting the inner crossing-out at 2p instead of p² (slower but still correct).
Returning primes for n < 2.

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Sieve of Eratosthenes

Code pattern to memorize

sieve: for p where !composite[p]: cross out p*p, p*p+p, ...

Rules to remember

1Unmarked ⟹ prime.
2Cross multiples from p².
3O(n log log n).

Use this pattern when

All primes up to a bound
Precomputing prime tables

Choose another pattern when

Just one primality check — use √n trial division

Interview takeaway

Need all primes up to n? Sieve, don't trial-divide each.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternA core fresher pattern: Sieve of Eratosthenes. Master it on small inputs and it transfers to harder problems.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Prime Number
Single-number primality via √n trial division.
Count Primes
Coming soon
Same sieve, return the count.

Same pattern