Use sieve to find prime numbers.

The idea here is to check every number less than or equal to N is prime or not. Those who are prime just add them in an array and return the array at the end of the function.

• Creat...read more

The idea here is similar to approach 1, which is to check every number less than or equal to ‘N’ is prime or not. The difference is that we are not running a loop till ‘N-1’ to che...read more

The idea here to use the Sieve of Eratosthenes. Sieve of Eratosthenes is used to find all the prime numbers less than or equal to ‘N’. It creates a boolean array of size ‘N+1’ and marks all the entries as true. After the function ends, all the entries marked with false are not the prime numbers.

• Create an empty array named as 'RESULT' to store the prime numbers.
• Call a function 'SIEVE_OF_ERATOSTHENES'(N) that returns an array and store it in the 'RESULT' array, i.e., 'RESULT' = 'SIEVE_OF_ERATOSTHENES'(N).
• Return the 'RESULT' array.

int[] 'SIEVE_OF_ERATOSTHENES'(int N):

• Create an empty array named 'TEMP' to store the output of this function.
• This function is finding all the prime numbers less than or equal to ‘N’.
• Create a boolean array named 'IS_PRIME' of size ‘N+1’ and initialize all the values to true.
• Run a loop with variable ‘i’ from 2 to ‘√N’, in each iteration:
  • If 'IS_PRIME'[i] == true, which means ‘i’ is a prime number so, we have to run a loop from variable ‘j’ = ‘i^2, i^2+i, i^2+2i, …, to N’:
    • Mark 'IS_PRIME'[j] = false.
• Finally, run a loop from ‘i’ = 2 to ‘N’, and add i to the 'TEMP' array if 'IS_PRIME'[i] == true.
• Return the 'TEMP' array.

O(N), where ‘N’ is the number given in the problem.

Since in the sieveOfEratosthenes function, we are making an array “IS_PRIME” of size ‘N+1’.

O(N log(logN)), where ‘N’ is the number given in the problem.

Refer to this for the asymptotic analysis of the Sieve of Eratosthenes.

'''

    Time Complexity: O(N log(logN))

    Space Complexity: O(N),



    where N is the number given in the problem.

'''



import math





def sieveOfEratosthenes(n):

    temp = []

    isPrime = [True for i in range(n + 1)]



    for i in range(2, int(math.sqrt(n)) + 1):

        if isPrime[i] == True:

            for j in range(i * i, n + 1, i):

                isPrime[j] = False



    for i in range(2, n + 1):

        if isPrime[i] == True:

            temp.append(i)



    return temp





def findAllPrimes(n):

    result = []



    result = sieveOfEratosthenes(n)

    return result

/*
    Time Complexity: O(N log(logN))
    Space Complexity: O(N),

    where 'N' is the number given in the problem.
*/

// Function to find the All Prime Numbers.
vector < int > sieveOfEratosthenes(int n) {
    // Create an empty vector to store the result.
    vector < int > temp;
    // Create a bool vector for mark the prime.
    vector < bool > isPrime(n + 1, true);

    for (int i = 2; i <= sqrt(n); i++) {
        // If i is prime, then mark all j from i^2,i^2+i,...n false.
        if (isPrime[i] == true) {
            for (int j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }

    // Run a loop to add the prime numbers in the temp vector.
    for (int i = 2; i <= n; i++) {
        if (isPrime[i] == true) {
            temp.push_back(i);
        }
    }

    return temp;
}

vector < int > findAllPrimes(int n) {
    // Create an empty vector to store the result.
    vector < int > result;
    // Call the function for finding all the Primes numbers.
    result = sieveOfEratosthenes(n);
    return result;
}

/*
    Time Complexity: O(N log(logN))
    Space Complexity: O(N),

    where 'N' is the number given in the problem.
*/

import java.util.ArrayList;

public class Solution {
    // Function to find the All Prime Numbers.
    public static ArrayList < Integer > sieveOfEratosthenes(int n) {
        // Create an empty vector to store the result.
        ArrayList < Integer > temp = new ArrayList < Integer > ();
        // Create a bool vector for mark the prime.
        boolean[] isPrime = new boolean[n + 1];
        for (int i = 2; i <= n; i++) {
            isPrime[i] = true;
        }

        for (int i = 2; i * i <= n; i++) {
            // If i is prime, then mark all j from i^2,i^2+i,...n false.
            if (isPrime[i] == true) {
                for (int j = i * i; j <= n; j += i) {
                    isPrime[j] = false;
                }

            }

        }

        // Run a loop to add the prime numbers in the temp vector.
        for (int i = 2; i <= n; i++) {
            if (isPrime[i] == true) {
                temp.add(i);
            }
        }

        return temp;
    }

    public static ArrayList < Integer > findAllPrimes(int n) {
        // Create an empty vector to store the result.
        ArrayList < Integer > result = new ArrayList < Integer > ();
        // Call the function for finding all the Primes numbers.
        result = sieveOfEratosthenes(n);
        return result;
    }
}