Find all the primes from 2 to n, using the Sieve of Eratosthenes [closed]

Question

Closed. This question needs details or clarity. It is not currently accepting answers.

---

Want to improve this question? Add details and clarify the problem by editing this post.

Closed 8 years ago.

Improve this question

I have a word problem I am trying to solve but am getting stuck on a key part.

Convert the following English description into Python code.

Initialize n to be 100. Initialize numbers to be a list of numbers from 2 to n, but not including n. With results starting as the empty list, repeat the following as long as numbers contains any numbers.

• Add the first number in numbers to the end of results.

• Remove every number in numbers that is evenly divisible by (has no remainder when divided by) the number that you had just added to results.

How long is result?

When n is 100, the length of results is 25.

So far I have understood to set n = 100, and a range(2, 100), results = [] and that the result will be an append situation as in results.append(numbers[]), but I am having a mental block figuring the key of "Remove every number in numbers that is divisible by the number that was added to results".

======after a couple minutes=======

As Michael0x2a said - this is a problem when i have to implement an algorithm that finds all the primes from 2 to n, using the Sieve of Eratosthenes.

I think I can continue to deal with this problem.

Thank's a lot for your answers guys.

Answer 1

n = 100
numbers = range(2,100)
results = []
while len(numbers) > 0:
    results.append(numbers[0])
    numbers = [number for number in numbers if number % results[-1] != 0]
print len(results)

Answer 2

The following:

Add the first number in numbers to the end of results.

...is not the same as:

results.append(numbers[])

To access the first number in a list, you can use the first index.

Thus:

numbers[0] ## would be the first "number" in numbers

---

Further, to do the following:

But I am having a mental block figuring the key of "Remove every number in numbers that is divisible by the number that was added to results".

...you will need some way of testing what a number is divisible by, which means you'll need to use modulo:

some_number % some_other_number

If there's no remainder, the modulo will result in a zero.