Scientific Calculator

silentmatt/primes

By Matthew Crumley

Generate all the prime numbers from 0 to n using the Sieve of Eratosthenes

Tagged: number-theory primes

// Find composite numbers up to n
sieve = function(n) {
    // 0 and 1 are composite
    var A = [true, true];
    A[n] = true; // Force A to go from 0 to n
    var i = 2;
    while (i^2 <= n) -> (
        if (not A[i]) ->(
            var j = i^2;
            while (j <= n) -> (
                A[j] = true;
                j += i;
            );
        );
        i += 1;
    );
    A;
};

primes = function(n) {
    var composite = sieve(n);
    filter(n -> not composite[n], range(n));
};

spam? | offensive?