# BEGIN QUESTION name: q1 manual: false points: 2
Question 1. Write a function called sieve
that takes in a positive integer n
and returns a set
of the prime numbers less than or equal to n
. Use the Sieve of Eratosthenes to find the primes.
# BEGIN SOLUTION
def sieve(n):
"""
Generate a set of prime numbers less than or equal to a positive integer.
"""
# BEGIN SOLUTION
is_prime = [True for _ in range(n + 1)]
p = 2
while p ** 2 <= n:
if is_prime[p]:
for i in range(p ** 2, n + 1, p):
is_prime[i] = False
p += 1
is_prime[0]= False
is_prime[1]= False
return set(i for i in range(n + 1) if is_prime[i])
# END SOLUTION
# END SOLUTION
# BEGIN TESTS
sieve(1) == set()
True
sieve(2) == {2}
True
sieve(3) == {2, 3}
True
# HIDDEN
sieve(20) == {2, 3, 5, 7, 11, 13, 17, 19}
True
""" # BEGIN TEST CONFIG
points: 1
hidden: true
""" # END TEST CONFIG
sieve(100) == {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}
True
# END TESTS
# END QUESTION