isPrime.md

Prompt

Write an algorithm that checks if a number is prime. Then identify its time complexity.

Approach

We know that a prime number is one that is divisible only by itself and 1, so we know that there is a set of numbers we could iterate through, dividing our input number n by each, to determine whether n is divisible by any of them and therefore not prime. What exactly are the constraints on that set, though?

Assuming that n is a positive whole number, right away it's obvious that we don't need to check any numbers less than 2 or greater than n - 1.

But we can do better. Is there a number less than n that acts as a transition point dividing the set of whole numbers between 2 and n - 1, allowing us to set aside part of the set as redundant? Indeed there is! That transition point is the square root of n. Why? Because any number that is greater than the square root of n and by which n is also divisible has to be multiplied by a number less than the square root of n to equal n. If that doesn't seem obvious, consider this framing: any two numbers that are both greater than the square root of n, multiplied by each other, will produce a value greater than n (because n is the product of two smaller numbers).

The execution is straightforward:

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

It could also be written like so:

function isPrime(n) {
	for (let i = 2; i * i <= n; i++) {
		if (n % i === 0) {
			return false
		}
	}
	return true
}

Examples

console.log(isPrime(11)) // => true
console.log(isPrime(21)) // => false
console.log(isPrime(2)) // => true
console.log(isPrime(4)) // => false

Time Complexity

The first version of the function makes the time complexity clearer: O(√n). In the worst case (where n is prime), the function must cycle through √n steps in the for loop, performing a constant operation at each step.