How to resolve the algorithm Sieve of Eratosthenes step by step in the ALGOL W programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Sieve of Eratosthenes step by step in the ALGOL W programming language
Table of Contents
Problem Statement
The Sieve of Eratosthenes is a simple algorithm that finds the prime numbers up to a given integer.
Implement the Sieve of Eratosthenes algorithm, with the only allowed optimization that the outer loop can stop at the square root of the limit, and the inner loop may start at the square of the prime just found. That means especially that you shouldn't optimize by using pre-computed wheels, i.e. don't assume you need only to cross out odd numbers (wheel based on 2), numbers equal to 1 or 5 modulo 6 (wheel based on 2 and 3), or similar wheels based on low primes. If there's an easy way to add such a wheel based optimization, implement it as an alternative version.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Sieve of Eratosthenes step by step in the ALGOL W programming language
Source code in the algol programming language
begin
% implements the sieve of Eratosthenes %
% s(i) is set to true if i is prime, false otherwise %
% algol W doesn't have a upb operator, so we pass the size of the %
% array in n %
procedure sieve( logical array s ( * ); integer value n ) ;
begin
% start with everything flagged as prime %
for i := 1 until n do s( i ) := true;
% sieve out the non-primes %
s( 1 ) := false;
for i := 2 until truncate( sqrt( n ) )
do begin
if s( i )
then begin
for p := i * i step i until n do s( p ) := false
end if_s_i
end for_i ;
end sieve ;
% test the sieve procedure %
integer sieveMax;
sieveMax := 100;
begin
logical array s ( 1 :: sieveMax );
i_w := 2; % set output field width %
s_w := 1; % and output separator width %
% find and display the primes %
sieve( s, sieveMax );
for i := 1 until sieveMax do if s( i ) then writeon( i );
end
end.
begin
% implements the sieve of Eratosthenes %
% only odd numbers appear in the sieve, which starts at 3 %
% s( i ) is set to true if ( i * 2 ) + 1 is prime %
procedure sieve2( logical array s ( * ); integer value n ) ;
begin
% start with everything flagged as prime %
for i := 1 until n do s( i ) := true;
% sieve out the non-primes %
% the subscripts of s are 1 2 3 4 5 6 7 8 9 10 11 12 13... %
% which correspond to 3 5 7 9 11 13 15 17 19 21 23 25 27... %
for i := 1 until truncate( sqrt( n ) ) do begin
if s( i ) then begin
integer ip;
ip := ( i * 2 ) + 1;
for p := i + ip step ip until n do s( p ) := false
end if_s_i
end for_i ;
end sieve2 ;
% test the sieve2 procedure %
integer primeMax, arrayMax;
primeMax := 100;
arrayMax := ( primeMax div 2 ) - 1;
begin
logical array s ( 1 :: arrayMax);
i_w := 2; % set output field width %
s_w := 1; % and output separator width %
% find and display the primes %
sieve2( s, arrayMax );
write( 2 );
for i := 1 until arrayMax do if s( i ) then writeon( ( i * 2 ) + 1 );
end
end.
You may also check:How to resolve the algorithm Pell's equation step by step in the Swift programming language
You may also check:How to resolve the algorithm Word frequency step by step in the Liberty BASIC programming language
You may also check:How to resolve the algorithm Terminal control/Cursor positioning step by step in the Julia programming language
You may also check:How to resolve the algorithm Comments step by step in the Monte programming language
You may also check:How to resolve the algorithm Rename a file step by step in the Clipper programming language