List All Prime Numbers up to N
Solve this ProblemEasy10–15 min
Topics
BasicsLoopsMath
Companies
TCSInfosysWipro
Given a non-negative integer
n, return every prime number from 2 up to and including n, in increasing order.
The trial divisionTrial Division per CandidateTesting each candidate number independently with the same up-to-√i divisibility check used in Check if a Number Is Prime. approach simply repeats the single-number primality check for every candidate from 2 to n. The Sieve of EratosthenesSieve of EratosthenesMarking every multiple of each prime found as composite, so later candidates can be checked with a single array lookup instead of their own division loop. flips the problem around: instead of asking "is this one prime?" over and over, it marks off every multiple of each prime as it's found, so by the end, anything never marked simply must be prime.
Test Case 1:
Input:n = 10
Output:[2, 3, 5, 7]
Explanation:Every prime from 2 up to and including 10.
Test Case 2:
Input:n = 1
Output:[]
Explanation:No primes exist at or below 1.
Test Case 3:
Input:n = 2
Output:[2]
Explanation:2 is the smallest prime.
Constraints
- ◆
0 ≤ n ≤ 1000
Try the Dry Run
Approach & Solutions
Trial Division for Each CandidateGood
Test every number from 2 to n: for each one, run the same trial-division check up to its own square root. Whatever passes gets collected into the result.
Time
O(n√n)Space
O(π(n)) for the outputJava
1class Solution {
2 public int[] listPrimes(int n) {
3 int[] temp = new int[n + 1];
4 int count = 0;
5 for (int i = 2; i <= n; i++) {
6 boolean isPrime = true;
7 for (int j = 2; j * j <= i; j++) {
8 if (i % j == 0) {
9 isPrime = false;
10 break;
11 }
12 }
13 if (isPrime) {
14 temp[count] = i;
15 count++;
16 }
17 }
18 int[] result = new int[count];
19 for (int k = 0; k < count; k++) {
20 result[k] = temp[k];
21 }
22 return result;
23 }
24}Sieve of EratosthenesOptimal
Instead of testing each number from scratch, mark multiples as you go: start with every number from 2 to n assumed prime, then for each prime p found, cross off every multiple of p (2p, 3p, 4p, ...) as not prime. Whatever is never crossed off by the time the sieve finishes is prime. No division or modulo is needed at all — just repeated marking.
Time
O(n log log n)Space
O(n)Java
1class Solution {
2 public int[] listPrimes(int n) {
3 boolean[] composite = new boolean[n + 1];
4 for (int p = 2; p * p <= n; p++) {
5 if (!composite[p]) {
6 for (int multiple = p * p; multiple <= n; multiple += p) {
7 composite[multiple] = true;
8 }
9 }
10 }
11 int count = 0;
12 for (int i = 2; i <= n; i++) {
13 if (!composite[i]) count++;
14 }
15 int[] result = new int[count];
16 int idx = 0;
17 for (int i = 2; i <= n; i++) {
18 if (!composite[i]) result[idx++] = i;
19 }
20 return result;
21 }
22}