JavaScript - different approaches to test if number is prime number
In this article, we would like to show different known approaches to check if given number is prime number using JavaScript.
Performace tests for the numbers from 0 to 100000 range:
| Tested solution | How fast is a solutuion? |
| Solution 1 | 360x faster than Solution 2 |
| Solution 2 | other solutions were compared to this one |
| Solution 3 | 17x faster than Solution 2 |
| Solution 4 | 9x faster than Solution 2 |
Note: tests were made on Ryzen 9 and Google Chrome Web Browser.
In this solution, we check if the tested input number is divided by some number from 2 up to floor(sqrt(number)) range.
Complexity: O(sqrt(n))
xxxxxxxxxxconst isPrimeNumber = (number) => { const limit = Math.floor(Math.sqrt(number)); for (let i = 2; i <= limit; ++i) { if (number % i === 0) { return false; } } return number >= 2;};// Usage example:console.log(isPrimeNumber(0)); // falseconsole.log(isPrimeNumber(1)); // falseconsole.log(isPrimeNumber(2)); // trueconsole.log(isPrimeNumber(3)); // trueconsole.log(isPrimeNumber(31)); // true
In this solution, we count number of the tested number factors - expected 2 in prime number case.
Complexity: O(n)
xxxxxxxxxxconst isPrimeNumber = (number) => { let count = 0; for (let i = 1; i <= number; ++i) { if (number % i === 0) { count += 1; } } return count == 2;};// Usage example:console.log(isPrimeNumber(0)); // falseconsole.log(isPrimeNumber(1)); // falseconsole.log(isPrimeNumber(2)); // trueconsole.log(isPrimeNumber(3)); // trueconsole.log(isPrimeNumber(31)); // true
In this solution, we check if the tested input number is divided by some number from 3 up to number (excluded) range.
Complexity: O(n/2)
xxxxxxxxxxconst isPrimeNumber = (number) => { if (number < 2) { return false; } if (number === 2) { return true; } if (number % 2 === 0) { return false; } for (let i = 3; i < number; i += 2) { if (number % i === 0) { return false; } } return true;};// Usage example:console.log(isPrimeNumber(0)); // falseconsole.log(isPrimeNumber(1)); // falseconsole.log(isPrimeNumber(2)); // trueconsole.log(isPrimeNumber(3)); // trueconsole.log(isPrimeNumber(31)); // true
In this solution, we check if the tested input number is divided by some number from 2 up to number (excluded) range.
Complexity: around O(n) - in practice algorithm ends job on factor detected.
xxxxxxxxxxconst isPrimeNumber = (number) => { if (number < 2) { return false; } if (number === 2) { return true; } for (let i = 2; i < number; ++i) { if (number % i === 0) { return false; } } return true;};// Usage example:console.log(isPrimeNumber(0)); // falseconsole.log(isPrimeNumber(1)); // falseconsole.log(isPrimeNumber(2)); // trueconsole.log(isPrimeNumber(3)); // trueconsole.log(isPrimeNumber(31)); // true
