- 4th Apr 2023
- 08:51 am
- Admin
Python Homework Help
Python Homework Question
Python Logical Puzzles, Games, and Algorithms: Sieve Eratosthenes
Python Homework Solution
Here's an implementation of the Sieve of Eratosthenes algorithm in Python:
def sieve_of_eratosthenes(n):
"""
Returns a list of prime numbers up to n using the Sieve of Eratosthenes algorithm.
"""
primes = [True] * (n+1)
primes[0] = primes[1] = False
for i in range(2, int(n**0.5)+1):
if primes[i]:
for j in range(i**2, n+1, i):
primes[j] = False
return [num for num, is_prime in enumerate(primes) if is_prime]
Here's how it works:
1. We start with a list of boolean values representing whether each number up to n is prime. Initially, we assume that all numbers are prime, so we set all values to True.
2. We mark 0 and 1 as non-prime since they are not prime by definition.
3. Starting from 2, we iterate through each number up to the square root of n. For each number i, if it is prime (i.e., its corresponding value in the primes list is True), we mark all multiples of i as non-prime by setting their corresponding values in the primes list to False. We only need to iterate up to the square root of n because any composite number greater than the square root of n must have a factor smaller than the square root of n, which we will have already marked as non-prime.
4. Finally, we return a list of all numbers up to n that are marked as prime in the primes list.
For example, calling sieve_of_eratosthenes(20) would return [2, 3, 5, 7, 11, 13, 17, 19], which are all the prime numbers up to 20.