| Projects does exist making me curious from a point of viwe as an assembler programmer. I'm asking me how they are to implement. Such projects are the the Ackermann function as well as the Easter algorithm. Then I found an article regarding the Sieve of Eratosthenes: |
|
From [Wikipedia]:
In mathematics, the sieve of Eratosthenes, one of a number of prime number sieves, is a simple, ancient algorithm for finding all prime numbers up to any given limit.
It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the multiples of 2.
The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime.
This is the sieve's key distinction from using trial division to sequentially test each candidate number for divisibility by each prime.
The sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes.
It is named after Eratosthenes of Cyrene, a Greek mathematician; although none of his works have survived, the sieve was described and attributed to Eratosthenes in the Introduction to Arithmetic by Nicomachus.
The sieve may be used to find primes in arithmetic progressions.
Implementation
The sieve of Eratosthenes can be expressed in pseudocode, as follows:
|
Input: an integer n > 1
Let A be an array of Boolean values, indexed by integers 2 to n,
initially all set to true.
for i = 2, 3, 4, ..., not exceeding vn:
if A[i] is true:
for j = i², i2+i, i²+2i, i²+3i, ..., not exceeding √n:
A[j] := false
Output: all i such that A[i] is true.
|
Note the function √ (sqrt(N)).
I implemeted it as described in the article
Tiny BASIC Square Root Routine.
The German Wikipedia shows a more detailed pseudocode which was the template for my program: |
const N = 10000
var gestrichen: array [2..N] of boolean
// Initialisierung des Primzahlfeldes
// Alle Zahlen im Feld sind zu Beginn nicht gestrichen
for i = 2 to N do
gestrichen[i] = false
end
// Siebe mit allen (Prim-) Zahlen i, wobei i der kleinste Primfaktor einer zusammengesetzten
// Zahl j = i*k ist. Der kleinste Primfaktor einer zusammengesetzten Zahl j kann nicht größer
// als die Wurzel von j <= n sein.
for i = 2 to sqrt(N) do
if not gestrichen[i] then
// i ist prim, gib i aus...
print i; ", ";
// ...und streiche seine Vielfachen, beginnend mit i*i
// (denn k*i mit k<i wurde schon als Vielfaches von k gestrichen)
for j = i*i to N step i do
gestrichen[j] = true
end
end if
end
// Gib die Primzahlen größer als Wurzel(n) aus - also die, die noch nicht gestrichen wurden
for i = sqrt(N)+1 to N do
if not gestrichen[i] then
// i ist prim, gib i aus
print i; ", ";
end if
end
|
|
The result are the sources SIEVE1 and SQRT.
Later I found an algorithm working less quare root — even less division making programming much easier. |
const N = 10000
var gestrichen: array [2..N] of boolean
// Initialisierung des Primzahlfeldes
// Alle Zahlen im Feld sind zu Beginn nicht gestrichen
for i = 2 to N do
gestrichen[i] = false
end
// Siebe mit allen (Prim-) Zahlen i, wobei i der kleinste Primfaktor einer zusammengesetzten
// Zahl j = i*k ist. Der kleinste Primfaktor einer zusammengesetzten Zahl j kann nicht größer
// als die Wurzel von j <= n sein.
for i = 2 to sqrt(N) do
if not gestrichen[i] then
// i ist prim, gib i aus...
print i; ", ";
// ...und streiche seine Vielfachen, beginnend mit i*i
// (denn k*i mit k<i wurde schon als Vielfaches von k gestrichen)
for j = i*i to N step i do
gestrichen[j] = true
end
end if
end
// Gib die Primzahlen größer als Wurzel(n) aus - also die, die noch nicht gestrichen wurden
for i = sqrt(N)+1 to N do
if not gestrichen[i] then
// i ist prim, gib i aus
print i; ", ";
end if
end
|
| The result is the source SIEVE2, here with the option to set limit by command line input. |