Code doodling: isPrime

Then I’ll run the code on my laptop and time the results for each algorithm testing for primes in the ranges 1–10¹, 1–10², 1–10³, 1–10⁴, 1–10⁵, and 1–10⁶.AlgorithmsIntuition about primes (knowing some math helps here):a number is not a prime if it is divisible by any number besides 1 and itselfany number can be expressed as the product of factors prime numbersan even number besides 2 cannot be prime because it would be divisible by 2a number expressed as a product of factors cannot have a factor greater than the value of its own square rootthe square root of a whole positive number is generally less than or equal to 1/2 the number (exceptions are 2 and 3)Because I’m timing my algorithms using the JavaScript console.time command, and running a series of ranges, I am automatically adding an extra iteration for the set of ranges..I won’t include that iteration through the range of numbers tested in stating the Big O for the algorithm.1..First TryTo start I will just iterate through all values in a range and test to see which are prime by dividing each number by every number in the range until a primes is found or none is found indicating a prime was found..In the worst case, when the number is prime the algorithm is Big O(n)..In reality the number of iterations is less then n because when a number is determined to be not prime the iteration stops and there are more non-prime numbers than prime numbers.function isPrime(n) { for (let i = 2; i < n; i++) { if (n % i == 0) return false; } return true;}console.time("check");for (let range = 1; range < 7; range++) { let n = Math.pow(10,range); for (let i = 1; i < n; i++) { let prime = isPrime(i); }}console.time("check");2..SieveFinding that sieves can be used to determine primes, the second algorithm will create a sieve a prime numbers that can be used to test numbers with successively greater values against numbers found to be prime..The idea is to start with small primes and then check each subsequent number to see if it is divisible by these primes and therefore not prime itself.This algorithm involves capturing primes in a data structure so there is a cost in space for using a sieve..The algorithm is optimized by seeding the sieve with 2 and 3, the lowest value primes and then only test odd numbers..The Big(O) for this algorithm is n*n/2 because we only test 1/2 the numbers in the range by excluding even numbers, but we test an ever growing list of captured primes..In fact, the Big O is a less the n²/2 because the number of captured primes is far less the quantity of numbers tested.const sieve = [2, 3];function findPrimes(n) { //test odd numbers only for (let i = 5; i <= n; i += 2) { let prime = true; //check every new number against divisibility by existing primes for (let j = 0; j <= sieve.length; j++) { if (i % sieve[j] === 0) { prime = false; } } if (prime) sieve.push(i); }}for (let range = 1; range < 7; range++) { let n = Math.pow(10, range); console.log("range", n) console.time("check"); findPrimes(n); // console.log(i, "Prime 1", isPrime(i)) console.timeEnd("check");}3..Half the Numbers3..Half the NumbersIn this algorithm, I abandon the sieve but focus on the looking for factors of the number tested for prime that are less then 1/2 the number.. More details

Leave a Reply