JavaScript Program to Check Prime Number

A prime number is a very important topic in number theory. They find their applications in a very wide domain in the real world. They are said to be "the heart of cryptography".

Any positive number greater than 1 which is only divisible by two numbers $i.e.$ 1 and the number itself is called a prime number. This means there is no possible way to divide a prime number without getting a remainder.

Let's have a look at a few examples for better understanding:

• 13 can only be divided by 1 and 13 because we will receive the remaining if we try to divide 13 by any other number such as 7 (the remainder will be 6).
• Similarly, 12 can be divided by $1, 2, 3, 4$, and $6$; hence it is a non-prime number.

It is easily noticeable that 2 is the smallest possible prime number, and interestingly it is the only even prime number out there.

The first 20 prime numbers are as given below:

Various methods are there to check whether a number is prime or not, and these methods are known as primality tests.

Methods to Check Prime Number in JavaScript

Example 1: Using While/For Loop

One of the most basic approaches to detect if a number (say x) is a prime number or not is to check whether there exists any divisor (say d) of x such that $1<d<x$.

Also, we know that for any number x, there does not exist any divisor d such that $d>\frac{x}{2}$ so what exactly we will do is we will search if there exists any number in the range $[2, x/2]$ such that it divides $x$ then we can conclude the given number is not a prime number otherwise it is.

Code:

Output: 1

Output: 2

Output : 3

Please note that since we are using the random function to get the number as a random value between 0 to 99, the output may vary when we run the above code.

Complexity Analysis:

• Time Complexity :
  As we are iterating from 2 to n/2 the time complexity is $O(n)$.
• Auxiliary Space:
  Since we are not using any extra space constant extra space is needed; hence overall space complexity is $O(1)$.

Now, if we apply simple mathematical knowledge, we can heavily optimize the time complexity part of our code to find prime numbers in javascript. The thing is to consider the complementary divisors $i.e.$ for any divisor d the number n/d will also be a divisor, and it is known as the complementary divisor.

For example:
Let's assume n to be 100 and d to be 5 then $100/5=20$ will be a complementary divisor, and for $d=25$, $100/25=4$ will also be a complementary divisor.

So, how can we use this for our benefit ? It is easily noticeable that if we take account of both the divisors and complementary divisors, then we need to iterate till $\sqrt{n}$ only because after $\sqrt{n}$ divisor starts repeating.

Let us understand this through an example :
Assume $n=100$ then the divisors and complementary divisors would be

You can observe that all the divisors can be found by iterating till $\sqrt{100}=10$ only.

To implement this, we only need to slightly modify our previous code.

Complexity Analysis:

• Time Complexity :
  As we are iterating from 2 to $\sqrt{n}$ the time complexity is $O(\sqrt{n})$.
• Auxiliary Space:
  Since we are not using any extra space so, constant extra space is needed; hence overall space complexity is $O(1)$.

Example 2: Using Sieve of Eratosthenes

Sieve of Eratosthenes is an algorithm used for finding all prime numbers in javascript within a given range from 1 to n, where n is an arbitrary number decided by you.

In this algorithm, initially, we assume all numbers to be prime then we start with 2 and mark all its multiples (greater than its square) up to n as non-prime numbers. Then we repeat this process for every number (say x) that is marked prime and mark all its multiples (greater than or equal to $x^2$) to be non-prime.

Algorithm:

• Declare a boolean array (say is_prime) of length n+1 (to maintain 1-based indexing).
• Mark all its entries to be true (prime).
• Iterate from $2$ to $\sqrt{n}$ and if a number (say i) is marked true $i.e.$ is_prime[i] = true mark all multiples of i (greater than $i^2$) to be false $i.e.$ is_prime[i*i], is_prime[i*(i+1)], ... = false.
• Check if is_prime[n] is false it means n is non-prime otherwise, it is a prime number.

Code:

• To check whether a given number (say x) is prime or not using the Sieve of Eratosthenes algorithm we need to first define a range in which x will lie.
• After defining a certain range, we will create a boolean array (say is_prime) of size range+1 (to maintain 1-based indexing), and then we will call an auxiliary function that will perform all the operations included in the Sieve of Eratosthenes method which has been described in the algorithm section given above.
• Then, we will just check the value is_prime at index x. If it is found true, then it means that x is a prime number; otherwise, it is a composite (non-prime) number.

Complexity Analysis:

• Time Complexity :
  The time complexity is $O(n\times \log{\log{n}})$.
• Auxiliary Space :
  As we are using a boolean array of size $n+1$ hence $O(n)$ extra space is required.

See Also

• Prime Number Program in C
• Prime Number Program in C++
• Prime Number Program in Java
• Prime Number Program in Python