An integer greater than one is a prime number if its only divisors are itself and one. Non-prime numbers are called composite. The number 18 is composite; it is a composite of 2×3×3. The number 19 is a prime number.
For finding all the small primes, one of the simplest methods is the Sieve of Eratosthenes (circa 240 BC). The method is to make a list of all the integers up to some number N; then mark the multiples of the next prime up through N. The numbers that are left unmarked are the primes. To illustrate, the first prime number is 2 (1 is not prime). The numbers 4, 6, 8, 10,... are marked. The next unmarked number is the next prime, that would be 3; mark all of its multiples - 6, 9, 12,... then repeat until halfway through the list.
Eratosthenes {born - 276 BC in Cyrene, North Africa (now Shahhat, Libya) died - 194 BC in Alexandria, Egypt}. Teachers included Lysanias of Cyrene and Ariston of Chios who had studied under Zeno, founder of the Stoic school of philosophy. Eratosthenes is remembered for his prime number sieve which is still an important tool in number theory research. Eratosthenes was a pioneer in geodesy and made the first accurate measurement of the circumference of the Earth.
Zeno 1.2 is an interpreter for the Zeno programming language. It is an easy to learn and is suitable for educational purposes.
const N : int := 5000
var a : array[N] of boolean
program
var i, j : int
init_a % initialize array
for i := 2...floor( N/2 ) do
for j := 2...floor( N/i ) do
a[i*j] := false % mark as not prime
end for
end for
j := 0
for i := 2...N do % output results
if a[i] then % is prime
put i : 6 ...
incr j
if (j mod 5) = 0 then % start new line
put ""
end if
end if
end for
end program
% initialize the array
procedure init_a
var i : int
for i := 1...N do
a[i] := true
end for
end procedure
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
AbCd Classics - free on-line books