Sieve of Eratosthenes

September 22, 2023

Sieve of Eratosthenes #

I’m looking for ways to stress-test QLogo. A suggestion that came up in my Google search was the Sieve of Eratosthenes. The algorithm goes like this:

erasthotenes(n):
    Create a list of all integers from 2 to n.
    Remove all multiples of primes up to the square root of n.
    The remaining list of numbers are the primes.

I don’t consider myself an expert in the Logo language. I wrote a complete interpreter for the language, but the interpreter itself is written in C++. So I am much more experienced writing C++ than QLogo.

Anyway, here is the code I finally hammered out in QLogo.

Sieve of Eratosthenes in QLogo #

to seq :m :n
    if :m > :n [output []]
    output se :m seq 1 + :m :n
end

to remove.multiples :n :L
    if empty? :L [output []]
    if 0 = modulo first :L :n [output remove.multiples :n butfirst :L]
    output se first :L remove.multiples :n butfirst :L
end

to walk.multiples :f :L
    if empty? :L [output []]
    if :f < first :L [output :L]
    output se first :L walk.multiples :f remove.multiples first :L butfirst :L
end

to Eratosthenes :n
    output se 1 walk.multiples sqrt :n seq 2 :n
end

; Example usage:
show Eratosthenes 500