Python Forum
sieve of eratosthenes implementation
Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
sieve of eratosthenes implementation
#4
Neither of those is the sieve of eratosthenes. While they both find prime numbers, this post asked a about a very specific method.
In the sieve of Eratosthenes you write all the number from 1 to a max value in a list.
Then starting with 2, you go through the list and eliminate all numbers divisible by that number. The next remaining number in the list (3) is used the same way. and so on until you reach the end of the list. When you reach the end of the list the only remaining number are primes.

Here is a very short implementation that is actually the sieve of Eratosthenes:
# The largest number in the sequence
max_value = 100

# Make sequence fro 1 to max_value
sequence = list(range(1, max_value + 1))

# Start at index 1 which has a value of 2
index = 1

# Check all values in sequence
while index < len(sequence):
    # Include any value that not the starting value or divisible by the starting value
    # In other words eliminate all values divisible by the starting value
    sequence = [number for number in sequence if number % sequence[index] != 0 or
                                                 number == sequence[index]]
    index += 1 # Move on to the next value

print(sequence)
Output:
[1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
Reply


Messages In This Thread
RE: sieve of eratosthenes implementation - by Clunk_Head - Dec-20-2019, 08:29 PM

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020