Prime numbers up to n

Problem

Given an integer N, list all prime numbers <= N in sorted order.

Examples

Example 1

Input: N = 30
Output: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Explanation: Primes less than or equal to 30.

Example 2

Input: N = 2
Output: [2]

Notes

• The naive primality test for each k by checking divisibility up to sqrt(k) yields O(N * sqrt(N)) overall and is inefficient for large N.
• Two standard fast methods are:
  • Sieve of Eratosthenes — simple and fast in practice (time ≈ O(N log log N)).
  • Linear (Euler) sieve — asymptotically O(N) and useful when you need the lowest prime factor for each number.

Follow up

• Implement the linear (Euler) sieve to generate primes in O(n) time (see Method 3 below).
• Create a generator that produces primes indefinitely (that is, without taking N as an input). Here is a solution - [Infinite Prime Generator](infinite-prime-generator).

Solution

We present three canonical approaches: a naive method (for clarity), the classic Sieve of Eratosthenes, and the linear (Euler) sieve. All three generate primes <= N (the naive method is included for completeness; prefer sieves for large N).

Method 1 — Naive primality checks

Intuition

Test each k in [2..N] for primality using trial division up to sqrt(k). This is straightforward but expensive when N is large.

Approach

1. For k from 2 to N:
   • Check divisibility of k by all integers d from 2 to floor(sqrt(k)).
   • If no divisor found, k is prime — append to the result list.

Edge cases: N < 2 returns an empty list.

Code

C++

#include <vector>
using namespace std;

class Solution {
 public:
  vector<int> primesUpto(int n) {
    vector<int> ans;
    if (n < 2) return ans;
    for (int k = 2; k <= n; ++k) {
      bool is_prime = true;
      for (int d = 2; 1LL * d * d <= k; ++d) {
        if (k % d == 0) { is_prime = false; break; }
      }
      if (is_prime) ans.push_back(k);
    }
    return ans;
  }
};

Java

class Solution {
  public List<Integer> primesUpto(int n) {
    List<Integer> ans = new ArrayList<>();
    if (n < 2) return ans;
    for (int k = 2; k <= n; ++k) {
      boolean isPrime = true;
      for (int d = 2; 1L * d * d <= k; ++d) {
        if (k % d == 0) { isPrime = false; break; }
      }
      if (isPrime) ans.add(k);
    }
    return ans;
  }
}

Python

class Solution:
  def primesUpto(self, n: int) -> list[int]:
    ans: list[int] = []
    if n < 2:
      return ans
    for k in range(2, n+1):
      is_prime = True
      d = 2
      while d * d <= k:
        if k % d == 0:
          is_prime = False
          break
        d += 1
      if is_prime:
        ans.append(k)
    return ans

Complexity

• ⏰ Time complexity: O(N * sqrt(N)) — for each k up to N we do trial division up to sqrt(k), so total work is proportional to the sum of sqrt(k) over k = 2..N (≈ N * sqrt(N) in worst-case reasoning).
• 🧺 Space complexity: O(1) extra space (excluding the output list of primes).

Method 2 — Sieve of Eratosthenes

This method is covered in detail here - [Sieve of Eratosthenes Algorithm](sieve-of-eratosthenes-algorithm).

Complexity

• ⏰ Time complexity: O(n log log n) in practice — the cost of marking multiples dominates but is sublinear per element; this is the classic bound for the sieve.
• 🧺 Space complexity: O(n), for the isPrime boolean array and the output list.

Method 3 — Euler sieve

Intuition

The Euler (linear) sieve visits every integer once, and for each number it marks composites using the list of primes discovered so far, guaranteeing each composite is marked exactly once by its smallest prime factor.

Approach

1. Maintain an array lp[0..N] of lowest prime factor (0 if none) and a list primes.
2. For i from 2 to N: if lp[i] == 0 then lp[i] = i and append i to primes.
3. For each prime p in primes (in increasing order):
   • If p > lp[i] or i * p > N break the inner loop.
   • Set lp[i * p] = p.
4. primes contains all primes <= N.

Edge cases: if N < 2 return an empty list.

Code

C++

#include <vector>
using namespace std;

class Solution {
 public:
  vector<int> primesUpto(int n) {
    vector<int> primes;
    if (n < 2) return primes;
    vector<int> lp(n + 1, 0);
    for (int i = 2; i <= n; ++i) {
      if (lp[i] == 0) { lp[i] = i; primes.push_back(i); }
      for (int p : primes) {
        long long v = 1LL * p * i;
        if (p > lp[i] || v > n) break;
        lp[v] = p;
      }
    }
    return primes;
  }
};

Go

package main

type Solution struct{}

func (s *Solution) PrimesUpto(n int) []int {
  if n < 2 { return []int{} }
  lp := make([]int, n+1)
  primes := make([]int, 0)
  for i := 2; i <= n; i++ {
    if lp[i] == 0 { lp[i] = i; primes = append(primes, i) }
    for _, p := range primes {
      v := p * i
      if p > lp[i] || v > n { break }
      lp[v] = p
    }
  }
  return primes
}

Java

import java.util.ArrayList;
import java.util.List;

class Solution {
  public List<Integer> primesUpto(int n) {
    List<Integer> primes = new ArrayList<>();
    if (n < 2) return primes;
    int[] lp = new int[n + 1];
    for (int i = 2; i <= n; ++i) {
      if (lp[i] == 0) { lp[i] = i; primes.add(i); }
      for (int p : primes) {
        long v = 1L * p * i;
        if (p > lp[i] || v > n) break;
        lp[(int)v] = p;
      }
    }
    return primes;
  }
}

Python

class Solution:
  def primesUpto(self, n: int) -> list[int]:
    if n < 2:
      return []
    lp = [0] * (n + 1)
    primes: list[int] = []
    for i in range(2, n + 1):
      if lp[i] == 0:
        lp[i] = i
        primes.append(i)
      for p in primes:
        v = p * i
        if p > lp[i] or v > n:
          break
        lp[v] = p
    return primes

Complexity

• ⏰ Time complexity: O(n) — each composite number is marked exactly once by its smallest prime factor.
• 🧺 Space complexity: O(n), for the lp array and the primes list.