Sieve of Eratosthenes

eratosthenes-memory.pl

#!/usr/bin/env perl
use common::sense;

sub eratosthenes ($) {
    my ($n) = @_;
    my $nums = "\3";
    for my $i (2 .. sqrt($n)) {
        unless (vec($nums, $i, 1)) {
            for (my $m = $i ** 2; $m <= $n; $m += $i) {
                vec($nums, $m, 1) = 1;
            }
        }
    }
    my @nums;
    vec($nums, $_, 1) or push @nums, $_
        for 0 .. $n;
    @nums;
}

{ local $, = ', '; say eratosthenes 100; }
eratosthenes 20_000_000;

eratosthenes-speed.pl

#!/usr/bin/env perl
use common::sense;

sub eratosthenes ($) {
    my $n = shift;
    my @nums = (0, 0, 2 .. $n);
    for my $i (2 .. sqrt($n)) {
        if ($nums[$i]) {
            for (my $m = $i ** 2; $m <= $n; $m += $i) {
                $nums[$m] = 0;
            }
        }
    }
    grep +$_, @nums;
}

{ local $, = ', '; say eratosthenes 100; }
eratosthenes 20_000_000;

eratosthenes.c

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

#define GetBit(a, b) ((((char *) a)[(b) >> 3] >> ((b) & 7)) & 1)
#define SetBit(a, b) (((char *) a)[(b) >> 3] |= (1 << ((b) & 7)))
#define ClearBit(a, b) (((char *) a)[(b) >> 3] &= ~(1 << ((b) & 7)))

char *eratosthenes (long unsigned int n) {
    char *sieve;
    int i, j, m;

    sieve = calloc((n >> 3) + 1, sizeof(char));
    m = (int) sqrt((double) n);
    SetBit(sieve, 0);
    SetBit(sieve, 1);
    for (i = 2; i <= m; i++)
        if (!GetBit(sieve, i))
            for (j = i * i; j <= n; j += i)
                SetBit(sieve, j);
    return sieve;
}

int main() {
    int i, n = 100;
    char *primes = eratosthenes(n);

    for (i = 0; i < n; i++)
        if (!GetBit(primes, i))
            printf("%d\n", i);

    eratosthenes(20000000);

    return 0;
}

eratosthenes.py

#!/usr/bin/env python
import pprint

def eratosthenes(n):
    nums = [False] * 2 + [True] * (n - 1) 
    for i in xrange(int(n ** 0.5 + 1.5)): # stop at ``sqrt(n)``
        if nums[i]:
            for m in xrange(i ** 2, n + 1, i):
                nums[m] = False
    return [i for i, prime in enumerate(nums) if prime]

pprint.pprint(eratosthenes(100))
eratosthenes(20000000)

eratosthenes.rb

#!/usr/bin/env ruby

def eratosthenes(n)
    nums = [0, 0] + (2 .. n).to_a
    (2 .. Math.sqrt(n).to_i).each do |i|
        if nums[i].nonzero?
            (i ** 2 .. n).step(i) {|m| nums[m] = 0}
        end
    end
    nums.find_all {|m| m.nonzero?}
end

p eratosthenes(100)
eratosthenes(20_000_000)