Analyzing How to generate Prime Numbers in Javascript
Prime numbers are numbers that are divisible by only one and itself. This feature makes them unique as they are mostly used in modern cryptography for security. To this end, its generation is quite necessary. There are different methods of generating prime numbers and these methods can be applied in different methods.
These methods do the job but at a slow rate and takes a lot of memory (i.e. they have very high space and time complexities). I plan on analyzing some effective ways of generating first n prime numbers where n is a chosen number of integers in Javascript.
Checking all numbers if they are prime until exact number is gotten.
This involves checking all the numbers between 2 and n to confirm if they are prime numbers. This can be gotten as follows.
const checkIfPrime = (num) => {
for (var i = 2; i < num; i++) {
if (num % i === 0) {
return false;
}
}
return true;
};const generatePrimeNumbers = (noOfPrimes = 10) => {
let workingArray = [2];
// Returns the number of primes needed when we reach that limit
if (noOfPrimes < workingArray.length) {
return workingArray.slice(0, noOfPrimes);
}
// Checks for prime for only odd numbers after 3 or last value of gotten primes.
for ( let i = 2;
workingArray.length < noOfPrimes;
i ++ ) {
if (checkIfPrime(i)) {
workingArray.push(i);
}
}
return workingArray;
};
The code above first checks if a given number is a prime number by checking if it is divisible by any number below it. To throw more light, if you wish to check if 7is a prime, it will check if it is divisible by 2, if true, then it is not a prime, if false, iteration occurs and it tries for 3 until it gets to 6 at which it still isn’t divisible, hence it is a prime.
In terms of time and space complexity, the time complexity is around O(m*n) and a linear space complexity. This works but it very slow and could take too much CPU load hence the need for a better solution.
Changing the top limit to check its factors.
To illustrate this point, let us see the illustration of all the factors of 36.
2 x 18
3 x 12
4 x 9
6 x 6 ---> Mid line
9 x 4
12 x 3
18 x 2If you look closely at the factors of the number 36 and try to replicate this for other numbers, you will notice that the factors of a number are totally replicated after the square root of that number. This will help greatly in reducing the number of times that we check the factors of a particular number as we will use the upper limit as the square root of the number as seen below.
const checkIfPrime = (num) => {
for (var i = 2; i < Math.ceil(sqrt(num)); i++) {
if (num % i === 0) {
return false;
}
}
return true;
};
… Code followsIn terms of time and space complexity, the time complexity is around O(m*LogN) because the square root makes n become LogN and a linear space complexity. This greatly reduces the amount of mathematically computations to be made but it can still be better.
Skip checks for even numbers
We all know that even numbers are numbers that are divisible by 2 and you would have noticed that as we iterate, we also iterated over 2 too, hence multiples of 2 was also checked. Lets take that out by tweaking the start limit and step as follows:
const checkIfPrime = (num) => {
if (num === 2) return true;
for (var i = 3; i <Math.ceil(sqrt(num)); i+= 2) {
if (num % i === 0) {
return false;
}
}
return true;
};
… Code followsFrom the little tweak seen there, we return 2 if we are testing for 2, but from 3 upwards, we iterate of over steps of 2. For example, while checking if 51 is prime, we check 2, 3, 5, 7 and return false if they are factors and return true if they aren’t.
This is the fastest we have now but it can still be faster by reducing the possible number of iterations for larger numbers.
Skip Check for multiples of primes
This method was pointed out by a friend of mine Daniel Adepoju. Thanks Bro.
If we decide to check if 101 is a prime, the square root would be 10.01… but the Math.ceil(101) would be 11, hence we are to check if 3, 5, 7, 9 are factors else it is a prime.
Looking closely, you would notice that 3 is a factor of 9 hence it is most definitely divisible by 3, so 9 should also be skipped. If we decide to do this for larger numbers, we will notice that we only have to check if the number n is divisible by primes. Hence, we need to find a way to pass only the previous primes to this function. See as follows:
const checkIfPrime = (num) => {
if (num === 2) return true;
for (let i = 3; i <Math.ceil(sqrt(num)); I += 2) {
if (num % i === 0) {
return false;
}
}
return true;
};const generatePrimeNumbers = (noOfPrimes = 10, lastArr = []) => {
let workingArray = [2];
// Replace working array with latest array of primes
if (Array.isArray(lastArr) && lastArr.length > 1) {
workingArray = lastArr;
}
// Returns the number of primes needed when we reach that limit if (Array.isArray(lastArr) && noOfPrimes < lastArr.length) {
return lastArr.slice(0, noOfPrimes);
}
// Checks for prime for only odd numbers after 3 or last value of gotten primes. for (
let i = workingArray.length === 1 ? 3 : workingArray[workingArray.length - 1] + 2;
workingArray.length < noOfPrimes;
i += 2) {
if (checkIfPrime(i, workingArray)) {
workingArray.push(i);
}
}
return workingArray;
};
We have used logic to greatly increase our computation speed and we have accomplished a great feat. This can also be tweaked by making use of closures so it can remember the last state of the prime number list. Most likely this could be implemented if you need to frequently check first n primes from user input.
We could still go one step further to greatly increase our computation speed by using the Sieve of Eratosthenes.
Sieve of Eratosthenes
This is a mathematical way of generating primes introduced by Eratosthenes of Cyrene dated around 276 BC.
The image above helps you understand how exactly this is done. While we have been checking if a particular number is prime, the Sieve of Eratosthenes looks to check which numbers are prime within a given range by crossing out multiples of that number until that particular range is covered.
For example, to get the primes between 0 and 20, we start from 2 which is a prime and cancel out multiples of 2 which become composites (numbers that are not prime). These composites are 4, 6, 8, 12, 14, 16, 18. Then we move to 3 multiples of 3 are 6, 9, 12, 15, 18; multiples of 4 are 8, 12, 16 and finally multiples of 5 (which is Math.ceil(20)) are 10, 15.
Looking closely, we would notice that 2, 3, 5, 7, 11, 13, 17, 19 are not multiples of any number, hence they are prime numbers. This greatly increases the speed of computation especially when you wish to get primes within a large range.
Since we want to get the first n prime numbers, the trick is to take a calculated guess on the possible number of primes that can be gotten from a particular max range, generate the primes within that range and return only the number of primes you need.
This can be gotten as follows.
const checkPrimeWithSoE = (primesNeededString = 10) => {
return new Promise((resolve) => {
const primesNeeded = Number(primesNeededString);
if (primesNeeded < 1) return [];
// Returns an empty array if primes is less than 1 if (primesNeeded === 1) return [2];
// Returns only 2 as prime if one is needed if (primesNeeded === 2) return [2, 3];
// Returns 2, 3 as only primes if only two are needed. // Generates an array of indices from 0 to maximum range (square of then number of primes needed) and populates it with true to show that at the beginning all numbers are primes. const primeArrayMap = new Array(primesNeeded * primesNeeded).fill(true); // We loop through the numbers and change their values for multiples of all numbers till the number of primes needed. let i = 2;
while (i <= primesNeeded) {
if (primeArrayMap[i]) {
for ( let multiple = i * i;
multiple < primeArrayMap.length;
multiple += i ) {
primeArrayMap[multiple] = false;
}
}
i++;
}
// We resolve the promise with the indices of the true values as they are the only numbers that arent multiples of numbers// The array is sliced to get the exact number of prime numbers we need. resolve(
primeArrayMap.map((prime, i) => {
if (prime) return i;
return undefined;
}).filter(Boolean).slice(1, primesNeeded + 1));
});
};
In the function above, we took a calculated guess that the number of primes we need will always be gotten from the square of that number of primes. For example, if you need 10 primes, it will always be gotten from range of 0–100. 50 primes can always be gotten from range of 0–2500 etc.
In terms of time complexity, this method is far better as it has a Big O of
O(Nlog(logN))
Where N is the maximum range to get the primes. This shows that this method is the fastest amonth those mentioned.
It also has its caveat as in terms of Space complexity, it is very high due to the amount of data it saves while generating the primes
CONCLUSION
While we have continually found ways of making the generation of primes faster by efficiently checking if a particular number is a prime to generating a list of prime numbers for a particular range, they are not without their demerits.
The constant check for primes takes time and computation power due to the number of times it checks if a number has factors. The sieve method is computationally faster but takes too much space for large numbers as it has to generate an array of large lengths to which some computers might not be able to handle.
To this end, we will be looking into some better ways of generating prime numbers in articles to come.
Stay tuned.
PS. I will love to see your reviews and constructive criticism so I could improve this.
