How to resolve the algorithm Sieve of Eratosthenes step by step in the S-BASIC programming language

Published on 12 May 2024 09:40 PM
#S-basic

How to resolve the algorithm Sieve of Eratosthenes step by step in the S-BASIC 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 S-BASIC programming language

Source code in the s-basic programming language

comment
   Find primes up to the specified limit (here 1,000) using
   classic Sieve of Eratosthenes
end

$constant limit = 1000
$constant false = 0
$constant true = FFFFH

var i, k, count, col = integer
dim integer flags(limit)

print "Finding primes from 2 to";limit

rem - initialize table
for i = 1 to limit
  flags(i) = true
next i

rem - sieve for primes
for i = 2 to int(sqr(limit))
  if flags(i) = true then
     for k = (i*i) to limit step i
        flags(k) = false
     next k
next i

rem - write out primes 10 per line
count = 0
col = 1
for i = 2 to limit
   if flags(i) = true then
      begin
         print using "#####";i;
         count = count + 1
         col = col + 1
         if col > 10 then
            begin
               print
               col = 1
            end
      end
next i
print
print count; " primes were found."

end

You may also check:How to resolve the algorithm Happy numbers step by step in the Eiffel programming language
You may also check:How to resolve the algorithm Möbius function step by step in the AutoHotkey programming language
You may also check:How to resolve the algorithm Maximum triangle path sum step by step in the 360 Assembly programming language
You may also check:How to resolve the algorithm Semordnilap step by step in the Factor programming language
You may also check:How to resolve the algorithm Align columns step by step in the JavaScript programming language