Need help creating a sieve of Eratosthenes in Scratch

Arithmetic, algebra, number theory, sequence and series, analysis, ...
Post Reply
jkibbe
Posts: 1
Joined: Tue Nov 19, 2013 4:34 pm

Need help creating a sieve of Eratosthenes in Scratch

Post by jkibbe » Tue Nov 19, 2013 4:38 pm

Here's what I have so far:

http://scratch.mit.edu/projects/14460081/

I have been trying to make it work for a while now, but it seems to get hung up on perfect squares and maybe multiples of 5. I think it is because I am trying to use multiple if/else blocks instead of a while block (Scratch doesn't have these). I've always been able to find a workaround, but now I'm just confused. Any advice is greatly appreciated!

RagingCain
Posts: 3
Joined: Wed Apr 29, 2015 3:31 pm

Re: Need help creating a sieve of Eratosthenes in Scratch

Post by RagingCain » Wed Apr 29, 2015 4:04 pm

This was a working solution in C#, not Scratch, but may help wanderers.

Code: Select all

    private static List<long> SieveOfEratosthenes()
    {
        List<long> PrimesFound = new List<long>();
        PrimesFound.Add(2);
 
        long SquareRoot = (long)Math.Sqrt(MAX_VALUE);
        BitArray Eliminated = new BitArray(MAX_VALUE + 1);
 
        for (long i = 3; i <= MAX_VALUE; i += 2)
        {
            if (Eliminated[i] != true)
            {
                PrimesFound.Add(i);
 
                if (i < SquareRoot)
                {
                    for (int j = i * i; j <= MAX_VALUE; j += 2 * i)
                    {
                        Eliminated[j] = true;
                    }
                }
            }
        }
 
        return PrimesFound;
    }

Post Reply