AlgoMaster Logo

Print All Primes Up to N

Last Updated: June 7, 2026

easy
5 min read

Understanding the Problem

A prime number is a whole number greater than 1 that has exactly two divisors: 1 and itself. The number 7 is prime because nothing between 2 and 6 divides it evenly. The number 9 is not prime, because 3 divides it. The number 1 is not prime by definition, since it has only one divisor. The smallest prime is 2, and it is the only even prime, because every other even number is divisible by 2.

Given an integer n, collect every prime from 2 up to and including n in increasing order. For n = 10, the primes in range are 2, 3, 5, and 7, so the answer is [2, 3, 5, 7].

Two cases need attention. When n is less than 2, there are no primes in range, so the answer is an empty array rather than an error. When n is exactly 2, the only prime in range is 2 itself, so the answer is [2].

Key Constraints:

  • n can be less than 2 → For n = 0 or n = 1, no number in range qualifies as prime, so the result must be an empty array. The loop or sieve has to produce nothing instead of failing.
  • n can be 2 → The smallest prime is 2, so an input of 2 returns [2]. Make sure the upper bound is inclusive so 2 is not skipped.
  • n can reach 10^6 → The range is large enough that the divisor test you choose matters. A sieve clears the whole range in near-linear time, while testing each number by trial division does more work as n grows.

Approach 1: Check Each Number

Intuition

The definition gives a direct test: walk through every candidate from 2 to n, test each one for primality, and keep the ones that pass.

The divisor search can stop early. If a number m has a divisor d larger than the square root of m, then m / d is a divisor smaller than the square root. Divisors come in pairs that multiply to m, and one member of each pair is always at or below the square root. So if no divisor exists up to the square root of m, none exists at all. That lets you stop the search at sqrt(m) instead of m - 1.

Algorithm

  1. Create an empty list to hold the result.
  2. Loop m from 2 to n inclusive.
  3. For each m, test divisors d from 2 while d * d <= m. If any d divides m evenly, m is not prime.
  4. If no divisor was found, append m to the list.
  5. Return the list as an array.

Example Walkthrough

Input:

10
n

Walk through m from 2 to 10. For m = 2, the divisor loop never runs because 2 * 2 is already greater than 2, so 2 is prime and gets appended. The same holds for 3. For m = 4, the divisor 2 satisfies 2 * 2 <= 4 and divides 4 evenly, so 4 is rejected. The value 5 has no divisor up to its square root, so it is kept. The value 6 is divisible by 2 and rejected, 7 is kept, 8 and 9 are rejected by divisors 2 and 3, and 10 is rejected by 2. The collected result is [2, 3, 5, 7].

0
2
1
3
2
5
3
7
result

Code

Each candidate pays for its own divisor search, and that search gets more expensive as the numbers grow. The work is also repetitive: every even number is tested against 2, every multiple of 3 against 3, over and over. What if you marked off the multiples once instead of rediscovering them for each candidate?

Approach 2: Sieve of Eratosthenes

Intuition

The sieve assumes every number from 2 to n is prime, then removes the ones that cannot be. The removal is driven by the primes themselves: once you know 2 is prime, every larger multiple of 2 (4, 6, 8, and so on) is composite, so you cross them all out in one sweep. Move to the next number still standing, which is 3, cross out its multiples, and continue. Whatever survives is prime.

What makes this efficient is where each sweep starts. When you process a prime p, you begin crossing out at p * p, not at 2 * p. Every multiple of p smaller than p * p has a factor smaller than p, and that smaller factor was a prime processed earlier. When you reach p = 5, the multiples 10, 15, and 20 were already crossed out by 2 and 3, so the first new multiple to remove is 25, which is 5 * 5. This also means the outer loop only needs to run while p * p <= n, because any composite at most n has a prime factor at most √n.

The marking sweep for the primes 2 and 3 looks like this on the numbers up to 10:

The green entries survived every sweep and are prime. The red entries were crossed out as multiples of 2 or 3.

Algorithm

  1. If n < 2, return an empty array.
  2. Create a boolean array isPrime of size n + 1, set every entry to true, then set indices 0 and 1 to false.
  3. For each p from 2 while p * p <= n, if isPrime[p] is true, mark every multiple p * p, p * p + p, p * p + 2p, and so on up to n as false.
  4. Collect every index from 2 to n whose entry is still true.
  5. Return those indices as an array.

Example Walkthrough

Input:

10
n

Start with indices 2 through 10 all marked prime. The outer loop runs while p * p <= 10, so it covers p = 2 and p = 3. For p = 2, begin crossing out at 2 * 2 = 4 and step by 2, removing 4, 6, 8, and 10. For p = 3, begin at 3 * 3 = 9 and step by 3, removing 9. The next value would be p = 4, but 4 * 4 = 16 is greater than 10, so the loop stops. The indices still marked prime are 2, 3, 5, and 7. The collected result is [2, 3, 5, 7].

0
2
1
3
2
5
3
7
result

Code