All Prime Numbers less than or equal to N

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.

• Create an empty array named as 'RESULT' to store the prime numbers.
• Run a loop with variable ‘i’ from 2 to ‘N’ and in each iteration do:
  • Check whether ‘i’ is prime or not, call the function 'IS_PRIME'(i), which has a return type bool. It returns true if ‘i' is a prime number, else it returns false.
  • If 'IS_PRIME'(i) == true, then add i to the 'RESULT' array.
• Return the 'RESULT' array.

bool 'IS_PRIME'(int n):

• This function is checking whether the number ‘N’ is prime or not.
• Run a loop with a variable ‘i’ from 2 to N-1 because if ‘N’ is prime, then it is not having any divisors in the range [2, N-1] :
  • If ‘N’ % ‘i’ == 0, which implies that i is a divisor of ‘N’, so simply return false.
• If the above loop is completed, then that it is guaranteed that ‘N’ is a prime number, so return true.

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 check whether ‘N’ is prime or not in this approach.

It is clear that if ‘i’ divides ‘N’ completely, then ‘N/i’ also divides ‘N’ completely.  So, we just run a loop to the square root of ‘N’ by using the above property. Those who are prime just add them into the array and return the array at the end of the function.

• Create an empty array named as 'RESULT' to store the prime numbers.
• As we know that 1 is not a prime nor a composite number, so run a loop with variable ‘i’ from 2 to ‘N’ and in each iteration do:
  • Check whether ‘i’ is prime or not, call the function 'IS_PRIME'(i), which has a return type bool. It returns true if i is a prime number, else it returns false.
  • If 'IS_PRIME'(i) == true, then add i to the 'RESULT' array.
• Return the 'RESULT' array.

bool 'IS_PRIME'(int n):

• This function is checking whether the number ‘N’ is prime or not.
• Run a loop with a variable ‘i’ from 2 to sqrt(N) :
  • If ‘N’ % ‘i’ == 0, which implies that ‘i’ is a divisor of ‘N’, so simply return false.
• If the above loop is completed that it is guaranteed that ‘N’ is a prime number, so return true

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.