How to resolve the algorithm Sieve of Eratosthenes step by step in the Yabasic programming language

Published on 12 May 2024 09:40 PM
#Yabasic

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

Source code in the yabasic programming language

#!/usr/bin/yabasic

// ---------------------------
// Prime Sieve Benchmark --
// "Shootout" Version    --
// ---------------------------
// usage:
//     yabasic sieve8k.yab 90000


SIZE = 8192
ONN = 1 : OFF = 0
dim flags(SIZE)

sub main()
    
    cmd = peek("arguments")
    if cmd = 1 then
       iterations = val(peek$("argument"))
       if iterations = 0 then print "Argument wrong. Done 1000." : iterations = 1000 end if
    else
       print "1000 iterations."
       iterations = 1000
    end if
    
    for iter = 1 to iterations
        count = 0
        for n= 1 to SIZE : flags(n) = ONN: next n
        for i = 2 to SIZE
            if flags(i) = ONN then
               let k = i + i
               if k < SIZE then
                 for k = k to SIZE step i
                    flags(k) = OFF
                 next k
               end if
               count = count + 1                 
            end if
        next i
    next iter
    print "Count: ", count  // 1028
end sub

clear screen

print "Prime Sieve Benchmark\n"

main()

t = val(mid$(time$,10))

print "time: ", t, "\n"
print peek("millisrunning")

You may also check:How to resolve the algorithm Rot-13 step by step in the Jsish programming language
You may also check:How to resolve the algorithm ABC problem step by step in the SNOBOL4 programming language
You may also check:How to resolve the algorithm Sorting algorithms/Comb sort step by step in the REXX programming language
You may also check:How to resolve the algorithm Elliptic Curve Digital Signature Algorithm step by step in the C++ programming language
You may also check:How to resolve the algorithm Date manipulation step by step in the C++ programming language