How to resolve the algorithm Sieve of Eratosthenes step by step in the REXX programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Sieve of Eratosthenes step by step in the REXX 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 REXX programming language
Source code in the rexx programming language
/*REXX program generates and displays primes via the sieve of Eratosthenes algorithm.*/
parse arg H .; if H=='' | H=="," then H= 200 /*optain optional argument from the CL.*/
w= length(H); @prime= right('prime', 20) /*W: is used for aligning the output.*/
@.=. /*assume all the numbers are prime. */
#= 0 /*number of primes found (so far). */
do j=2 for H-1; if @.j=='' then iterate /*all prime integers up to H inclusive.*/
#= # + 1 /*bump the prime number counter. */
say @prime right(#,w) " ───► " right(j,w) /*display the prime to the terminal. */
do m=j*j to H by j; @.m=; end /*strike all multiples as being ¬ prime*/
end /*j*/ /* ─── */
say /*stick a fork in it, we're all done. */
say right(#, 1+w+length(@prime) ) 'primes found up to and including ' H
/*REXX program generates primes via a wheeled sieve of Eratosthenes algorithm. */
parse arg H .; if H=='' then H=200 /*let the highest number be specified. */
tell=h>0; H=abs(H); w=length(H) /*a negative H suppresses prime listing*/
if 2<=H & tell then say right(1, w+20)'st prime ───► ' right(2, w)
@.= '0'x /*assume that all numbers are prime. */
cw= length(@.) /*the cell width that holds numbers. */
#= w<=H /*the number of primes found (so far).*/
!=0 /*skips the top part of sieve marking. */
do j=3 by 2 for (H-2)%2; b= j%cw /*odd integers up to H inclusive. */
if substr(x2b(c2x(@.b)),j//cw+1,1) then iterate /*is J composite ? */
#= # + 1 /*bump the prime number counter. */
if tell then say right(#, w+20)th(#) 'prime ───► ' right(j, w)
if ! then iterate /*should the top part be skipped ? */
jj=j * j /*compute the square of J. ___*/
if jj>H then !=1 /*indicates skip top part if j > √ H */
do m=jj to H by j+j; call . m; end /* [↑] strike odd multiples ¬ prime */
end /*j*/ /* ─── */
say; say right(#, w+20) 'prime's(#) "found up to and including " H
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────────────*/
.: parse arg n; b=n%cw; r=n//cw+1;_=x2b(c2x(@.b));@.b=x2c(b2x(left(_,r-1)'1'substr(_,r+1)));return
s: if arg(1)==1 then return arg(3); return word(arg(2) 's',1) /*pluralizer.*/
th: procedure; parse arg x; x=abs(x); return word('th st nd rd',1+x//10*(x//100%10\==1)*(x//10<4))
/*REXX pgm generates and displays primes via a wheeled sieve of Eratosthenes algorithm. */
parse arg H .; if H=='' | H=="," then H= 200 /*obtain the optional argument from CL.*/
w= length(H); @prime= right('prime', 20) /*w: is used for aligning the output. */
if 2<=H then say @prime right(1, w) " ───► " right(2, w)
#= 2<=H /*the number of primes found (so far).*/
@.=. /*assume all the numbers are prime. */
!=0; do j=3 by 2 for (H-2)%2 /*the odd integers up to H inclusive.*/
if @.j=='' then iterate /*Is composite? Then skip this number.*/
#= # + 1 /*bump the prime number counter. */
say @prime right(#,w) " ───► " right(j,w) /*display the prime to the terminal. */
if ! then iterate /*skip the top part of loop? ___ */
if j*j>H then !=1 /*indicate skip top part if J > √ H */
do m=j*j to H by j+j; @.m=; end /*strike odd multiples as not prime. */
end /*j*/ /* ─── */
say /*stick a fork in it, we're all done. */
say right(#, 1 + w + length(@prime) ) 'primes found up to and including ' H
/*REXX program generates primes via sieve of Eratosthenes algorithm.
* 21.07.2012 Walter Pachl derived from above Rexx version
* avoid symbols @ and # (not supported by ooRexx)
* avoid negations (think positive)
**********************************************************************/
highest=200 /*define highest number to use. */
is_prime.=1 /*assume all numbers are prime. */
w=length(highest) /*width of the biggest number, */
/* it's used for aligned output.*/
Do j=3 To highest By 2, /*strike multiples of odd ints. */
While j*j<=highest /* up to sqrt(highest) */
If is_prime.j Then Do
Do jm=j*3 To highest By j+j /*start with next odd mult. of J */
is_prime.jm=0 /*mark odd mult. of J not prime. */
End
End
End
np=0 /*number of primes shown */
Call tell 2
Do n=3 To highest By 2 /*list all the primes found. */
If is_prime.n Then Do
Call tell n
End
End
Exit
tell: Parse Arg prime
np=np+1
Say ' prime number' right(np,w) " --> " right(prime,w)
Return
You may also check:How to resolve the algorithm String comparison step by step in the Falcon programming language
You may also check:How to resolve the algorithm Knuth shuffle step by step in the SETL programming language
You may also check:How to resolve the algorithm Look-and-say sequence step by step in the Rust programming language
You may also check:How to resolve the algorithm Count occurrences of a substring step by step in the SenseTalk programming language
You may also check:How to resolve the algorithm Sorting algorithms/Permutation sort step by step in the PHP programming language