The Sieve of Eratosthenes

The Sieve of Eratosthenes is a simple, well-known algorithm for finding Prime Numbers. It was created by the Ancient Greek mathemetician Eratosthenes.

The algorithm can be written in a single line of APL code which finds all the prime numbers upto and including X:

      (2=+⌿0=(⍳X)∘.|⍳X)/⍳X

For example, to list all the prime numbers upto 100:

      (2=+⌿0=(⍳X)∘.|⍳X)/⍳X←100
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

It's interesting to compare the brevity of this single line of code with a typical implementation written in the C programming language. In C, the code might look as follows:

/* Sieve of Eratosthenes in C */
#include <stdio.h>
#include <stdlib.h>

int main (int argc, char **argv)
{
    unsigned long n, x, y, *primes;
 
    /* Get the upper limit value, n */   
    if (argc != 2) {
        fprintf (stderr, "Usage is e.g:\n    %s 10\n", argv[0]);
        return -1;
    }
    
    n = strtoul (argv[1], NULL, 0);
    if (n <= 0) {
        fprintf (stderr, "Argument must be greater than 0\n");
        return -1;
    }
    
    /* Run the sieve algorithm */
    primes = (unsigned long *) calloc (n+1, sizeof (unsigned long)); 
    for (x = 2; x <= n; x++) {
        for (y = 2; y <= x; y++) {
            if (x * y > n)
                break;
            primes [x * y] = 1;
        }
    }
    
    /* Print the results */
    for (x = 2; x <= n; x++) {
        if (primes [x] == 0)
            printf ("%d ", x);
    }
    printf ("\n");
    return 0;
}

And of course in C we would need to compile and link the program before we could run it. In APL, you just type in the expression.

CategoryShowcases