# 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
In [4]:
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
In [10]:
sieve(1) == set()
Out[10]:
True
In [12]:
sieve(2) == {2}
Out[12]:
True
In [13]:
sieve(3) == {2, 3}
Out[13]:
True
In [15]:
# HIDDEN
sieve(20) == {2, 3, 5, 7, 11, 13, 17, 19}
Out[15]:
True
In [23]:
""" # 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}
Out[23]:
True
# END TESTS

# END QUESTION