Prime number

Given an integer, return true if it's a prime number, false otherwise.

Advanced

Instructions

Given an integer, return true if it's a prime number, false otherwise. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.

Write a function that takes an integer as input and returns true if it is a prime number, false otherwise.

Example

isPrime(4) // false
isPrime(3) // true

You can assume that the input integer is non-negative.

Tests

0/4

Function Call:

Expected:

isPrime(4)

false

Run test

isPrime(3)

true

Run test

Hidden Test

Run test

Hidden Test

Run test

See Solution

Solution

Basic idea

A number is prime if it is greater than 1 and has no divisors other than 1 and itself.
We can check if a number is prime by iterating from 2 to the square root of the number and checking if the number is divisible by any of these values.
The square root is used as the upper limit since factors repeat after the square root.

const isPrime = (myInt) => {
    if (myInt < 2) return false;
    for (let i = 2; i <= Math.sqrt(myInt); i++) {
        if (myInt % i === 0) return false;
    }
    return true;
}

Algorithm Detailed Explanation

If the input number is less than 2, return false since prime numbers are greater than 1.
Iterate from 2 to the square root of the input number. The square root is used as the upper limit since factors repeat after the square root.
Check if the input number is divisible by any of the values in the range.
If the input number is divisible by any value, return false.
If the input number is not divisible by any value, return true.

Complexity Analysis

The time complexity of this solution is O(sqrt(n)), where n is the input number. This is because we iterate from 2 to the square root of the input number to check for divisors. The space complexity is O(1) since we use a constant amount of extra space.

Any improvement idea? Share with us!