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

Published on 12 May 2024 09:40 PM
#Scratch

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

Source code in the scratch programming language

when clicked
    broadcast: fill list with zero (0) and wait
    broadcast: put one (1) in list of multiples and wait
    broadcast: fill primes where zero (0 in list

when I receive: fill list with zero (0)
    delete all of primes
    delete all of list
    set i to 0
    set maximum to 25
    repeat maximum
        add 0 to list
        change i by 1
    {end repeat}

when I receive: put ones (1) in list of multiples
    set S to sqrt of maximum
    set i to 2
    set k to 0
    repeat S
        change J by 1
        set i to 2
        repeat until i > 100
            if not (i = J) then
                if item i of list = 0 then
                    set m to (i mod J)
                    if (m = 0) then
                        replace item i of list with 1
        {end repeat until}
        change i by 1
        set k to 1
        delete all of primes
    {end repeat}
    set J to 1

when I receive: fill primes where zeros (0) in list
    repeat maximum
        if (item k of list) = 0 then
            add k to primes
        set k to (k + 1)
    {end repeat}

You may also check:How to resolve the algorithm Smith numbers step by step in the Ring programming language
You may also check:How to resolve the algorithm Compare length of two strings step by step in the Lua programming language
You may also check:How to resolve the algorithm Dining philosophers step by step in the E programming language
You may also check:How to resolve the algorithm Range consolidation step by step in the C++ programming language
You may also check:How to resolve the algorithm Increment a numerical string step by step in the Rust programming language