# BEGIN QUESTION
name: q1
points: 2

Question 1. Write a function called sieve that takes in a positive integer n and returns a sorted vector of the prime numbers less than or equal to n. Use the Sieve of Eratosthenes to find the primes.

# BEGIN SOLUTION

# BEGIN SOLUTION NO PROMPT
sieve = function(n) {
    is_prime = rep(TRUE, n)
    p = 2
    while (p^2 <= n) {
        if (is_prime[p]) {
            is_prime[seq(p^2, n, p)] = FALSE
        }
        p = p + 1
    }
    is_prime[1] = FALSE
    return(seq(n)[is_prime])
}
# END SOLUTION
. = " # BEGIN PROMPT
sieve = function(n) {
    ...
}
" # END PROMPT

# END SOLUTION

# BEGIN TESTS

testthat::expect_equal(length(sieve(1)), 0)

testthat::expect_equal(sieve(2), c(2))

testthat::expect_equal(sieve(3), c(2, 3))

# HIDDEN
testthat::expect_equal(sieve(20), c(2, 3, 5, 7, 11, 13, 17, 19))

. = " # BEGIN TEST CONFIG
points: 1
hidden: true
" # END TEST CONFIG
testthat::expect_equal(sieve(100), c(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))

# END TESTS

# END QUESTION