The Sieve of Eratosthenes

[bmass]

Hey there, I have an assignment which requires me to create a program to calculate and display all prime numbers from one, up to a number input by the user. I need to use the Sieve of Eratosthenes to do this; however I am not really sure how. I have been given to hint that Iit can be done by "Eliminating multiples by assigning 0 to certain elements of the array."

The chapter is on arrays in variables (e.g., var x : array 1 .. 12 := init ("whatever")), so I know that the hint is refering to certain variable in the array, but I am completely lost on how to implement the Sieve of Eratosthenes. If anyone could give me some tips or pointers, it would be greatly appreciated.

Or if it is easier to give me a tiny chunk of code, I could decipher it (although it would be nicer to figure this out on my own, I appreciate help of any kind). Thanks.

-Steve

[Tony]

you gonna need:

for loops
for i by n loops
and of course, arrays

ultimately after you are done looping, you want to be able to do

code:

if my_array(i) then    puts i, " is prime" else    puts i, " is not prime" end if

[Clayton]

@Tony: puts? methinks someones been doing too much programming in Ruby lately...

bmass: as well as above, you could jump ahead of your class and look into functions as well, you will find all of the tutorials you will need in the Turing Walkthrough. Read through them when you have time, and you will be ahead of your class in no time

[Ultrahex]

Sieve of Eratosthenes

Explanation:
The Sieve of Eratosthenes is a reverse way of determing the Prime Numbers,
Instead of finding the prime numbers by dividing until it reaches the number its checking to be prime, it goes the reverse (sorta ).

Basically lets say you have a number that is prime like 7
we all know 7 is prime,
7 makes the numbers, such as

7(2)=14
7(3)=21
7(4)=28
7(5)=35
7(6)=42
7(7)=49
...
7(n) = ?

all the numbers are not prime listed above.

ok
so all the multiples of a prime, is not prime is the basis of the algorithm.

2 is prime
2(2..infinity) is not prime

by above i mean that any number that is a multiple of 2 is not a prime. except 2*1=2 which is prime


so now you have to make a way of determining this in terms of code.

lets Start with PSEUDO:

get n
array notprimes size 1 to n of int
array checked size 1 to n of boolean

set all of checked to false


checked(1) is true %Set 1 as prime or not, your choice Here


for m 2..n
if checked(m) is false then
for k: m to rounded down ( n/ m)
checked (k*m) is true
end
end
end

%All That Are Not Checked Are Prime

--- This Is Not Complete But Maybe It Will Help You

[bmass]

@Ultrahex: Sorry, but I am completely confused by your response.

Tony wrote:

you gonna need:

for loops
for i by n loops
and of course, arrays

ultimately after you are done looping, you want to be able to do

code:

if my_array(i) then    puts i, " is prime" else    puts i, " is not prime" end if

I am not entirely sure what you mean by "for i by n loops" and the part that I am not understanding about that code is that it isn't comparing the array to anything. It is just saying if the variable is there, then display it (if you are suggesting that variables not representing a prime number should not exist, that is the part that I am having trouble with).

Freakman wrote:

bmass: as well as above, you could jump ahead of your class and look into functions as well, you will find all of the tutorials you will need in the Turing Walkthrough. Read through them when you have time, and you will be ahead of your class in no time

Thanks, but I am not sure that the class is going to be doing that. I am already 2 and a half weeks ahead and at the last chapter. I just wanted to finish off with Turing so that I can move onto PHP without getting mixed up (hopefully I will be able to finish before we start VB in class).

[Tony]

@Freakman: haha, Ruby is awesome, though lately I've been doing PHP mostly (and just a bit of Ruby).

@bmass:

code:

for i: 1 .. 10 by 2    put i end for

as for comparing arrays - we just need a statement that evaluates to a boolean value (true or false). So if the variable itself is boolean

code:

var myArray: array 1..1 of boolean

then it works just like

code:

if true then    put "yes, it's true!" end if

the above code will of course compile and execute in Turing.

[Ultrahex]

Pseudo Code
Used to describe the flow of a program and commands in which without a program specified, usually written in a SPOKEN language with programming terms used.

PseudoCode: output "Hello World"
Turing: put "Hello World"

Sieve of Eratosthenes
An Acient Algorithm Used to Determine Prime Numbers from 2 to n, where n is an integer.

Algorithm (Redefined For Your Purpose)
1. Make a List Of Numbers From 2 to n (LIST A)
2. Write the First Prime Number (which is 2)
3. Write Your Prime Number to a List (LIST B)
4. Cross off/Remove 2 and all multiples of 2 from your list (LIST A)
---- To Optimize This Step You Can Square the 2 because numbers before already have been crossed off.
5. Repeat Steps 2 to 4 Using The Next Not Crossed Off Number In List A

Pseudo Code: Sieve of Eratosthenes

Declare List A of Type INT
Declare List B of Type INT
Declare k of Type INT
Declare n of Type INT
input n

for each value from 2 to n
-add to List A
end

for each number in List A
-Add Number To List B
-for each number from 1 to n/(num in List A)
--Remove From List A
-end
end

For each number in List B
-Print Out Value
end

Conclusion
Hope This Helps, Since You Actually Brung It Up, I was wondering what the Sieve of Eratosthenes was, so i actually did write the program in turing really fast, my other pseudo code actually makes more sence for what you have to end up doing to manipulating Lists in Turing. But Other Then That that is the basis of what you have to do, Hope This Time It Helps

[Silent Avenger]

Wow nice use of Pseudo code Ultrahex very clear and understandable. I usually don't see many people use it.

[bmass]

Ultrahex wrote:

Declare List A of Type INT
Declare List B of Type INT
Declare k of Type INT
Declare n of Type INT
input n

for each value from 2 to n
-add to List A
end

for each number in List A
-Add Number To List B
-for each number from 1 to n/(num in List A)
--Remove From List A
-end
end

For each number in List B
-Print Out Value
end

This is quite helpful, I am just having trouble figuring out the bold parts. Adding and removing from lists. When you say create a list, what I am doing is an array for a variable, is this correct? If so, I am still having trouble figuring out how to add/remove values from an array/list. If not, please let me know how to declare a list. Thanks.

[Clayton]

yes, by a list he means declare an array, adding is as simple as making an "empty" element in your array hold some sort of value, and removing it is as simple as making an element holding a value some inconsequencial value like 0 in your case. You can also look up flexible arrays (which im sure most classes dont cover ) and use those instead, which allow for a much greater amount of dynamic use. either way, good luck with this.