Primes upto N Editorial

Practice Problem Link: Primes upto N | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a number, find all the prime numbers from 1 to that number.

Naive Approach

We can iterate over all the numbers from 1 to N, and check if the current number is prime, store it in an appropriate container.

Analysis

• Time Complexity: O(n * root(n)) // root(n) is required to check if a number is prime.
• Auxiliary Space Complexity: O(1)

Implementation

C++

bool isPrime(int n) {
   for(int i = 2; i * i <= n; i++) {
       if(n % i == 0) {
           return false;
       }
   }
   return true;
}
vector<int> primesUptoN(int n) {
   vector<int> answer;
   for(int i = 2; i <= n; i++) {
       if(isPrime(i) == true) {
           answer.push_back(i);
       }
   }
   return answer;
}

Java

class Solution {
   boolean isPrime(int n) {
       for(int i = 2; i * i <= n; i++) {
           if(n % i == 0) {
               return false;
           }
       }
       return true;
   }
   List<Integer> primesUptoN(int n) {
       ArrayList<Integer> answer = new ArrayList<Integer>();
       for(int i = 2; i <= n; i++) {
           if(isPrime(i) == true) {
               answer.add(i);
           }
       }
       return answer;
   }
}

Optimal Approach

We can precompute all the primes from 1 to N in N * log(logN) time complexity using the Sieve of Eratosthenes.

In this algorithm, we initially consider all the numbers from 1 to N to be primes, then we iterate over all the numbers from 2 to sqrt(N), and if we find a prime number, then we mark all its multiples as non-prime.

At the end of the algorithm, only the prime numbers remain unmarked and so we can decide if a number is prime in constant time.

Analysis

• Time Complexity: O(N * log(logN))
• Space Complexity: O(n)

Implementation

C++

vector<int> primesUptoN(int n) {
   bool isPrime[n + 1];
   for(int i = 2; i <= n; i++) {
       isPrime[i] = true;
   }
   isPrime[0] = isPrime[1] = false;
   for(int i = 2; i * i <= n; i++) {
       for(int j = i * i; j <= n; j += i) {
           if(isPrime[i] == true) {
               isPrime[j] = false;
           }
       }
   }
   vector<int> answer;
   for(int i = 2; i <= n; i++) {
       if(isPrime[i] == true) {
           answer.push_back(i);
       }
   }
   return answer;
}

Java

class Solution {
   List<Integer> primesUptoN(int n) {
       boolean isPrime[] = new boolean[n + 1];
       for(int i = 2; i <= n; i++) {
           isPrime[i] = true;
       }
       isPrime[0] = isPrime[1] = false;
       for(int i = 2; i * i <= n; i++) {
           for(int j = i * i; j <= n; j += i) {
               if(isPrime[i] == true) {
                   isPrime[j] = false;
               }
           }
       }
       ArrayList<Integer> answer = new ArrayList<Integer>();
       for(int i = 2; i <= n; i++) {
           if(isPrime[i] == true) {
               answer.add(i);
           }
       }
       return answer;
   }
}