JavaScript
// Finding Prime Numbers
// Method #1 Sieve of Eratosthenes - make a list of possible numbers, drop all of the non-primes and everything left is prime. Most efficient.
// Credit: http://stackoverflow.com/a/15471749/1265817
var eratosthenes = function(n) {
// Eratosthenes algorithm to find all primes under n
var array = [], upperLimit = Math.sqrt(n), output = [];
// Make an array from 2 to (n - 1)
for (var i = 0; i < n; i++) {
array.push(true);
}
// Remove multiples of primes starting from 2, 3, 5,...
for (var i = 2; i <= upperLimit; i++) {
if (array[i]) {
for (var j = i * i; j < n; j += i) {
array[j] = false;
}
}
}
// All array[i] set to true are primes
for (var i = 2; i < n; i++) {
if(array[i]) {
output.push(i);
}
}
return output;
};
console.log("eratosthenes list primes to 100000", eratosthenes(100000))
// Method #2 Get a list of prime numbers through n by checking each number individually. Less efficient for large numbers
var list_of_primes = function(n) {
var list = [];
for (i = 2; i < n; i++) {
if (is_prime(i)) {
list.push(i);
}
}
return list;
}
function is_prime(i) {
for (var c = 2; c <= Math.sqrt(i); ++c)
if (i % c === 0)
return false;
return true;
}
console.log("list primes to 1000",list_of_primes(1000))
console.log("check any number", is_prime(1),is_prime(971),is_prime(100000));
// Method #3 because cheating is fun! and primes are a set list of numbers so if calculating is too memory intense, just spew them all out manually. Absolutely not ideal when dealing with large sets, but it works for small sets easy enough.
// Here's a list of the first 10,000: https://primes.utm.edu/lists/small/10000.txt
var prime_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233,...