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.