Prime numbers are fascinating. They crop up pretty much randomly, so it is hard to find them. The examples on this page will be in ECMA Script.
A prime number is a number
n, divisible only by
n. Because of that, you can prove its primality by checking its divisibility from
This method is very inefficient. You may have noticed that you don't have to check past
Math.sqrt(n) because after that you just get duplicates
n % 2 !== 0, then
n % E !== 0 (
E being all even numbers). Ideally we only check divisibility with prime numbers, but it isn't practical to have a long list of primes. Generating them on the spot would be inefficient (even with elegant algorithms like Sieve of Eratosthenes). We can, however rule out divisors divisible by a small list of prime numbers. The optimal length of this list would increase with input size.
Checking in long if statements
(n === 2 || n === 3 || n === 5 || n === 7) is inefficient. We could have the loop iterating over every other
i instead of every
i to get rid of the
n === 2 in the if statement. You may have noticed that all primes (except 2) are odd
(2n+1). All primes (except 2 and three) are
6n + (2 or 4). All primes (except 2, 3, and 5) are
30 + (1, 7, 11, 13, 17, 19, 23, 29). You can go on to 2, 3, 5, and 7.