Computer Science 301 - 2017
Programming Language Translation
Practical 1, Week beginning 17 July 2017 - First Solutions
PROGRAM Sieve (Input, Output);
(* Sieve of Eratosthenes for finding primes 2 <= N <= Max
P.D. Terry, Rhodes University, 2017 *)
(* Modified and with suggested use of range checking pragmas *)
CONST
Max = 32000 (* largest number allowed *);
TYPE
SIEVES = ARRAY [2 .. Max] OF BOOLEAN;
VAR
I, N, K, Primes, It, Iterations : INTEGER (* counters *);
Uncrossed : SIEVES (* the sieve *);
Display : BOOLEAN;
BEGIN
Write('How many iterations '); Read(Input, Iterations);
Display := Iterations = 1;
Write('Supply largest number to be tested '); Read(Input, N);
IF N > Max THEN BEGIN
WriteLn(Output, 'N too large, sorry'); HALT
END;
WriteLn(Output, 'Prime numbers between 2 and ', N);
WriteLn(Output, '------------------------------------');
FOR It := 1 To Iterations DO BEGIN
Primes := 0 (* no primes yet found *);
FOR I := 2 TO N DO (* clear sieve *)
Uncrossed[I] := TRUE;
FOR I := 2 TO N DO (* the passes over the sieve *)
IF Uncrossed[I] THEN BEGIN
IF Display AND (Primes MOD 8 = 0) THEN WriteLn; (* ensure line not too long *)
Primes := Primes + 1;
IF Display THEN Write(Output, I:6);
K := I; (* now cross out multiples of I *)
REPEAT
Uncrossed[K] := FALSE;
K := K + I
UNTIL (K > N) OR (K < 0) (* ++++++++++++++ It looks silly but it works! ++++++++++++++ *)
END;
IF Display THEN WriteLn
END;
Write(Primes, ' primes')
END.
============================================================================================
PROGRAM Sieve (Input, Output);
(*$R+ +++++++ Switch Range checks on ++++++++++++++++++++++++++++ try this with TURBO *)
(* Sieve of Eratosthenes for finding primes 2 <= N <= Max
P.D. Terry, Rhodes University, 2017 *)
CONST
Max = 32000 (* largest number allowed *);
TYPE
SIEVES = ARRAY [2 .. Max] OF BOOLEAN;
VAR
I, N, K, Primes, It, Iterations : INTEGER (* counters *);
Uncrossed : SIEVES (* the sieve *);
Display : BOOLEAN;
BEGIN
Write('How many iterations '); Read(Input, Iterations);
Display := Iterations = 1;
Write('Supply largest number to be tested '); Read(Input, N);
IF N > Max THEN BEGIN
WriteLn(Output, 'N too large, sorry'); HALT
END;
WriteLn(Output, 'Prime numbers between 2 and ', N);
WriteLn(Output, '------------------------------------');
FOR It := 1 To Iterations DO BEGIN
Primes := 0 (* no primes yet found *);
FOR I := 2 TO N DO (* clear sieve *)
Uncrossed[I] := TRUE;
FOR I := 2 TO N DO (* the passes over the sieve *)
IF Uncrossed[I] THEN BEGIN
IF Display AND (Primes MOD 8 = 0) THEN WriteLn; (* ensure line not too long *)
Primes := Primes + 1;
IF Display THEN Write(Output, I:6);
K := I; (* now cross out multiples of I *)
REPEAT
Uncrossed[K] := FALSE; (* be prepared to crash here if K went "negative last time *)
K := K + I (* K might go "negative" when K exceeds 32767 *)
UNTIL (K > N) (* +++++++++++++ OR (K < 0) looks silly? ++++++++++++++ *)
END;
IF Display THEN WriteLn
END;
Write(Primes, ' primes')
END.
========================================================================================
PARVA VERSIONS
Note that we have now used the array so that Element[N] corresponds to number N,
and not, as in the kinky original, where Element[N-2] corresponds to number N.
If you are going to clean up code, do it properly!
// Sieve of Eratosthenes for finding primes 2 <= n <= Max (Corrected Parva version)
// P.D. Terry, Rhodes University, 2017
void Main() {
const Max = 32000;
bool[] uncrossed = new bool[Max]; // the sieve
int i, n, k, it, iterations, primes = 0; // counters
read("How many iterations? ", iterations);
bool display = iterations == 1;
read("Supply largest number to be tested ", n);
if (n > Max) {
write("n too large, sorry");
return;
}
write("Prime numbers between 2 and " , n, "\n");
write("-----------------------------------\n");
it = 1;
while (it <= iterations) {
primes = 0;
i = 2;
while (i <= n) { // clear sieve
uncrossed[i-2] = true;
i = i + 1;
}
i = 2;
while (i <= n) { // the passes over the sieve
if (uncrossed[i]) {
if (display && (primes - (primes/8)*8 == 0))
write("\n"); // ensure line not too long
primes = primes + 1;
if (display) write(i, "\t");
k = i; // now cross out multiples of i
uncrossed[k] = false;
k = k + i;
while (k <= n) {
uncrossed[k] = false;
k = k + i;
}
}
i = i + 1;
}
it = it + 1;
if (display) write("\n");
}
write(primes, " primes");
} // Main
===============================================================================================
+++++++++ Making use of a little function for "mod" and a simpler while loop
// Sieve of Eratosthenes for finding primes 2 <= n <= Max (Another Corrected Parva version)
// P.D. Terry, Rhodes University, 2017
int mod (int a, int b) {
// Compensate for lack of % - returns a % b
return a - (a / b) * b;
} // mod
void Main() {
const Max = 32000;
bool[] uncrossed = new bool[Max]; // the sieve
int i, n, k, it, iterations, primes = 0; // counters
read("How many iterations? ", iterations);
bool display = iterations == 1;
read("Supply largest number to be tested ", n);
if (n > Max) {
write("n too large, sorry");
return;
}
write("Prime numbers between 2 and " , n, "\n");
write("-----------------------------------\n");
it = 1;
while (it <= iterations) {
primes = 0;
i = 2;
while (i <= n) { // clear sieve
uncrossed[i-2] = true;
i = i + 1;
}
i = 2;
while (i <= n) { // the passes over the sieve
if (uncrossed[i]) {
if (display && (mod(primes, 8) == 0))
write("\n"); // ensure line not too long
primes = primes + 1;
if (display) write(i, "\t");
k = i; // now cross out multiples of i
while (k <= n) {
uncrossed[k] = false;
k = k + i;
} // while
} // if
i = i + 1;
} // while i
it = it + 1;
if (display) write("\n");
} // iterations
write(primes, " primes");
} // Main
Home © P.D. Terry