Print all primes till N

Intuition:

A naive approach to print all prime numbers till N, is to check every number starting from 1 till N for prime. If the number is prime, it can be stored in a list. Once all the numbers are checked, the counter stores the required count.

Approach:

Declare a list to store all the primes till N.
Iterate from 2 to N, and check the current value for prime (using the optimal way). If found prime, store it in a list.
After the iterations are over, all the prime numbers are stored in the list.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
private:
    /* Function to find whether the
    number is prime or not */
    bool isPrime(int n) {
        
        /* Variable to store the 
        count of divisors of n */
        int count = 0;
        
        // Loop from 1 to square root of n
        for(int i = 1; i <= sqrt(n); ++i) {
            
            // Check if i is a divisor
            if(n % i == 0) {
                // Increment count
                count = count + 1;
                
                /* Check if counterpart divisor
                is different from original divisor */
                if(n / i != i) {
                    
                    // Increment count
                    count = count + 1;
                }
            }
        }
        
        // If count is 2, n is prime
        if(count == 2) return true;
        // Else not prime
        return false;
    }
    
public:
    // Function to get all primes till N
    vector<int> primeTillN(int n){
        
        // To store all the primes
        vector<int> primes;
        
        // Iterate from 1 to n
        for (int i = 2; i <= n; i++) {
            
            // Check if i is prime
            if (isPrime(i)){
                // If found prime, add it to the list
                primes.push_back(i);
            }
        }
        
        // Return the list
        return primes;
    }
};

int main() {
    int n = 7;
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    // Function call to get all primes till N
    vector<int> ans = sol.primeTillN(n);
    
    cout << "All primes till N are: " << endl;
    for(int i=0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
    
    return 0;
}
import java.util.ArrayList;

class Solution {
    // Function to find whether the number is prime or not
    private boolean isPrime(int n) {
        // Variable to store the count of divisors of n
        int count = 0;
        
        // Loop from 1 to square root of n
        for (int i = 1; i <= Math.sqrt(n); ++i) {
            // Check if i is a divisor
            if (n % i == 0) {
                // Increment count
                count = count + 1;
                
                /* Check if counterpart divisor is 
                different from original divisor */
                if (n / i != i) {
                    // Increment count
                    count = count + 1;
                }
            }
        }
        
        // If count is 2, n is prime
        return count == 2;
    }
    
    // Function to get all primes till N
    public ArrayList<Integer> primeTillN(int n){
        
        // To store all the primes
        ArrayList<Integer> primes = new ArrayList<>();
        
        // Iterate from 1 to n
        for (int i = 2; i <= n; i++) {
            
            // Check if i is prime
            if (isPrime(i)){
                // If found prime, add it to the list
                primes.add(i);
            }
        }
        
        // Return the list
        return primes;
    }
}

public class Main {
    public static void main(String[] args) {
        int n = 7;
        
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution(); 
        
        // Function call to get all primes till N
        ArrayList<Integer> ans = sol.primeTillN(n);
        
        System.out.println("All primes till N are: ");
        for(int i = 0; i < ans.size(); i++) {
            System.out.print(ans.get(i) + " ");
        }
    }
}
import math

class Solution:
    # Function to find whether 
    # the number is prime or not
    def isPrime(self, n):
        # Variable to store the count 
        # of divisors of n
        count = 0
        
        # Loop from 1 to square root of n
        for i in range(1, int(math.sqrt(n)) + 1):
            # Check if i is a divisor
            if n % i == 0:
                # Increment count
                count += 1
                
                # Check if counterpart divisor is 
                # different from original divisor
                if n // i != i:
                    # Increment count
                    count += 1
        
        # If count is 2, n is prime
        return count == 2
    
    # Function to get all primes till N
    def primeTillN(self, n):
        
        # To store all the primes
        primes = []
        
        # Iterate from 1 to n
        for i in range(2, n + 1):
            
            # Check if i is prime
            if self.isPrime(i):
                # If found prime, add it to the list
                primes.append(i)
        
        # Return the list
        return primes

if __name__ == "__main__":
    n = 7
    
    # Creating an instance of 
    # Solution class
    sol = Solution() 
    
    # Function call to get all primes till N
    ans = sol.primeTillN(n)
    
    print("All primes till N are: ")
    for i in ans:
        print(i, end=" ")
class Solution {
    /* Function to find whether the 
     number is prime or not */
    isPrime(n) {
        /* Variable to store the 
        count of divisors of n */
        let count = 0;
        
        // Loop from 1 to square root of n
        for (let i = 1; i <= Math.sqrt(n); ++i) {
            // Check if i is a divisor
            if (n % i === 0) {
                // Increment count
                count = count + 1;
                
                /* Check if counterpart divisor is 
                different from original divisor */
                if (n / i !== i) {
                    // Increment count
                    count = count + 1;
                }
            }
        }
        
        // If count is 2, n is prime
        return count === 2;
    }
    
    // Function to get all primes till N
    primeTillN(n) {
        
        // To store all the primes
        let primes = [];
        
        // Iterate from 1 to n
        for (let i = 2; i <= n; i++) {
            
            // Check if i is prime
            if (this.isPrime(i)){
                // If found prime, add it to the list
                primes.push(i);
            }
        }
        
        // Return the list
        return primes;
    }
}

const main = () => {
    let n = 7;
    
    /* Creating an instance of 
    Solution class */
    let sol = new Solution(); 
    
    // Function call to get all primes till N
    let ans = sol.primeTillN(n);
    
    console.log("All primes till N are: ");
    for (let i = 0; i < ans.length; i++) {
        process.stdout.write(ans[i] + " ");
    }
    console.log();
};

main();

Complexity Analysis:

Time Complexity: O(N^3/2) Checking all numbers from 1 to N for prime and checking if a number is prime or not will take O(N^1/2) TC.

Space Complexity: O(N / logN) Using a list to store all the primes. In the worst case, the number of prime numbers less than or equal to N is approximately N / logN.

Intuition:

An optimal approach to solve this problem is to use the Sieve of Eratosthenes algorithm which is an efficient algorithm to find all primes till N.

The main idea is to iteratively mark the multiples of each prime number starting from 2. This way, only prime numbers remain unmarked. The Sieve of Eratosthenes significantly reduces the number of operations compared to the naive approach, making it optimal for large values of N.

Approach:

Create a list to mark whether numbers up to n are prime, initializing all entries as prime.
Iterate through numbers starting from 2 up to n:
- If a number is identified as prime, store it in the result list.
- For each prime number, mark all its multiples as non-prime starting from its square, since smaller multiples will have already been marked.
Collect and return all numbers that remain marked as prime.

Dry Run:

Observation:

While marking the multiples of a prime number as not prime, it can be seen that some of the nodes are already marked as not prime by previous nodes. Thus, to avoid redundant checking of already marked nodes, the multiples of the prime number must be checked starting from the square of the number.

Solution:

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    // Function to get all primes till N
    vector<int> primeTillN(int n) {
    
        /* To store whether a number is prime or not
        where all numbers are marked as prime initially */
        vector<int> isPrime(n+1, 1); 
        
        // To store the prime number till N
        vector<int> ans;
        
        // Traverse from number 2 till N
        for(long long i=2; i <= n; i++) {
    
            //If the number is prime
            if(isPrime[i]) {
                // Store the number in the result
                ans.push_back(i);
                
                // Mark all its multiples as not prime
                for(long long val = i*i; val <= n; val += i) {
                    
                    // Marking multiples of i as not prime
                    isPrime[val] = false;
                }
            }
        }  
        // Return the result
        return ans;
    }
};

int main() {
    int n = 7;
    
    /* Creating an instance of 
    Solution class */
    Solution sol; 
    
    // Function call to get all primes till N
    vector<int> ans = sol.primeTillN(n);
    
    cout << "All primes till N are: " << endl;
    for(int i=0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
    
    return 0;
}
import java.util.*;

class Solution {
    // Function to get all primes till N
    public ArrayList<Integer> primeTillN(int n) {
    
        /* To store whether a number is prime or not
        where all numbers are marked as prime initially */
        boolean[] isPrime = new boolean[n + 1];
        for (int i = 0; i <= n; i++) {
            isPrime[i] = true;
        }
        
        // To store the prime numbers till N
        ArrayList<Integer> ans = new ArrayList<>();
        
        // Traverse from number 2 till N
        for (long i = 2; i <= n; i++) {
    
            // If the number is prime
            if (isPrime[(int) i]) {
                // Store the number in the result
                ans.add((int) i);
                
                // Mark all its multiples as not prime
                for (long val = i * i; val <= n; val += i) {
                    
                    // Marking multiples of i as not prime
                    isPrime[(int) val] = false;
                }
            }
        }  
        // Return the result
        return ans;
    }

    public static void main(String[] args) {
        int n = 7;
        
        /* Creating an instance of 
        Solution class */
        Solution sol = new Solution(); 
        
        // Function call to get all primes till N
        ArrayList<Integer> ans = sol.primeTillN(n);
        
        System.out.println("All primes till N are: ");
        for (int i = 0; i < ans.size(); i++) {
            System.out.print(ans.get(i) + " ");
        }
    }
}
class Solution:
    # Function to get all primes till N
    def primeTillN(self, n):
    
        # To store whether a number is prime or not
        # where all numbers are marked as prime initially
        isPrime = [1] * (n + 1)
        
        # To store the prime numbers till N
        ans = []
        
        # Traverse from number 2 till N
        for i in range(2, n + 1):
    
            # If the number is prime
            if isPrime[i]:
                # Store the number in the result
                ans.append(i)
                
                # Mark all its multiples as not prime
                for val in range(i * i, n + 1, i):
                    
                    # Marking multiples of i as not prime
                    isPrime[val] = False
        # Return the result
        return ans

if __name__ == "__main__":
    n = 7
    
    # Creating an instance of 
    # Solution class
    sol = Solution()
    
    # Function call to get all primes till N
    ans = sol.primeTillN(n)
    
    print("All primes till N are: ")
    for i in ans:
        print(i, end=" ")
class Solution {
    // Function to get all primes till N
    primeTillN(n) {
    
        /* To store whether a number is prime or not
        where all numbers are marked as prime initially */
        const isPrime = new Array(n + 1).fill(true);
        
        // To store the prime numbers till N
        const ans = [];
        
        // Traverse from number 2 till N
        for (let i = 2; i <= n; i++) {
    
            // If the number is prime
            if (isPrime[i]) {
                // Store the number in the result
                ans.push(i);
                
                // Mark all its multiples as not prime
                for (let val = i * i; val <= n; val += i) {
                    
                    // Marking multiples of i as not prime
                    isPrime[val] = false;
                }
            }
        }  
        // Return the result
        return ans;
    }
}

const sol = new Solution();

const n = 7;

// Function call to get all primes till N
const ans = sol.primeTillN(n);

console.log("All primes till N are: ");
for (let i = 0; i < ans.length; i++) {
    console.log(ans[i] + " ");
}

Complexity Analysis:

Time Complexity: O(N x log(logN)) The Sieve of Eratosthenes algorithm is used which takes O(N x log(logN)) time.

Space Complexity: O(N) The Sieve of Eratosthenes algorithm uses a boolean array to mark the numbers as prime or not prime taking O(N) space.

Problem List

Examples:

Constraints

Hints

Company Tags

Editorial

Intuition:

Approach:

Dry Run:

Solution:

Complexity Analysis:

Intuition:

Approach:

Dry Run:

Observation:

Solution:

Complexity Analysis:

Frequently Occurring Doubts

Interview Followup Questions

Notes

Code