This function works taking an input number and trying to divide it by all the numbers from 2 to the square root of the input number. If any of these numbers divides the original number exactly then that number cannot be prime.
The function also checks to see if the input number is less than 2 or not an integer and if so returns false.
Note we only have to check up to the square root of the input number as any factors greater than this will have a corresponding smaller factor pair.
Use the code to check if a number is prime!
See the code in action below. Choose a number and test whether it is prime.
isPrime(n) and leastFactor(n)
Click the Run button to display the results of the function calls isPrime(n) and leastFactor(n) and measure the execution time.
Here are several versions of the function isPrime(n) . All versions check the primality by trial division; so, all versions are, in a sense, brute force tests. However, note that the version with the fewest lines of code takes the longest to run for a large prime n – thus, not all brute force tests are created equal: Below is the source code of the functions for primality testing that are actually used on this page. This code works even faster than the fastest version listed above. Here only about a quarter of divisors under sqrt(n) are checked in the main for loop; the other three-quarters (multiples of 2, 3, or 5) are immediately eliminated in the initial checks, before entering the for loop: If you look at the source code of primefactors.js, you will notice additional browser-specific optimizations.
Note : A prime number (or a prime) is a natural number greater than 1 that has no positive divisors other than 1 and itself.
Improve this sample solution and post your code through Disqus
- JS- Home
- JS- Hello World !
- JS- Add Two Number
- JS- Swap Two Number
- JS- Odd Even Number
- JS- Factorial of Number
- JS- Prime Number
- JS- Reverse a Number
- JS- Armstrong Number
- JS- Palindrome Number
- JS- Verify Age of Person
- Print Any Patterns
- JS - Triangle of Star
- JS - Print Number Pattern
- JS - Print Alphabet Pattern
- Useful Resources
- JS- Interview Question
Feeling nerdier than usual last night, I was asking myself, and a math teacher (that’s Mrs. Jaye, to you), all sorts of questions about numbers, including prime numbers. Later on, I got to thinking: how would I determine what the prime numbers are in a given range? And then I thought about writing that program. And then I fell asleep — because…narcolepsy at 10:30 is called bed time.
I took two years of high school math (which I barely passed), and one highly remedial math course in college (it comprised football players and me). I have the math skills of your typical liberal arts major, so you are within your rights to challenge and/or laugh at my code.
A prime number, as a mathematician explained to me last night, is any number that can only be divided by itself, and 1 . A prime number shouldn’t be divisible by any more than two numbers. So, our goal is threefold:
- count up through a list of numbers, one whole integer at a time
- Determine the numbers by which that integer can be divided to make a whole number
- Determine if any of those numbers by which my integer can be divided are not 1 , or the integer itself
The first thing I thought was that I’d need two arrays: an array for regular integers and an array for prime numbers. I also set up the for loop to start at zero, rather than my start number. You’ll see why in a minute.
My thinking was that, as I count up, I'll need to keep track of the available numbers by which I should divide my integer. So I push my integer to my numArray . Also, inside of my for loop, I created a divisArray to keep track of the numbers by which I can divide my integer.
Discover the divisible numbers
Check and see if the number is prime
I cheated here. If I wanted to do this good and proper, I'd actually loop through my divisArray to find either 1 or the integer. I decided to use a much simpler logic: if it's prime, it must be divisible by only two numbers. Therefore, if there are more than two numbers in my divisArray , it's not prime.
Inside of my first for loop, I test the length of my divisArray . Not only that, I check to see if the integer is greater than, or equal to, my start variable. I use my start variable here, and not in my first for loop is because starting my for loop anywhere but zero means I never get to test to see if my integer is divisible by earlier numbers. e.g. If I start at 6, then I never get to test 0, 1, 2, 3, 4, 5.
The aforementioned code will produce an array called primeArray , which should contain my prime numbers. But maybe I want that to be pretty, and useful. In that case, I'll introduce some HTML, a dab o'CSS, and actually print out the result: