{
 "cells": [
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "<div class=\"cell border-box-sizing text_cell rendered\"><div class=\"prompt input_prompt\">\n",
    "</div><div class=\"inner_cell\">\n",
    "<div class=\"\">\n",
    "<pre>\n",
    "# BEGIN QUESTION\n",
    "name: q1\n",
    "manual: false\n",
    "points: 2\n",
    "</pre>\n",
    "</div>\n",
    "</div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**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."
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "<div class=\"cell border-box-sizing text_cell rendered\"><div class=\"prompt input_prompt\">\n",
    "</div><div class=\"inner_cell\">\n",
    "<div class=\"\">\n",
    "<pre>\n",
    "# BEGIN SOLUTION\n",
    "</pre>\n",
    "</div>\n",
    "</div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sieve(n):\n",
    "    \"\"\"\n",
    "    Generate a set of prime numbers less than or equal to a positive integer.\n",
    "    \"\"\"\n",
    "    # BEGIN SOLUTION\n",
    "    is_prime = [True for _ in range(n + 1)]\n",
    "    p = 2\n",
    "    while p ** 2 <= n:\n",
    "        if is_prime[p]:\n",
    "            for i in range(p ** 2, n + 1, p):\n",
    "                is_prime[i] = False\n",
    "        p += 1\n",
    "\n",
    "    is_prime[0]= False\n",
    "    is_prime[1]= False\n",
    "\n",
    "    return set(i for i in range(n + 1) if is_prime[i])\n",
    "    # END SOLUTION"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "<div class=\"cell border-box-sizing text_cell rendered\"><div class=\"prompt input_prompt\">\n",
    "</div><div class=\"inner_cell\">\n",
    "<div class=\"\">\n",
    "<pre>\n",
    "# END SOLUTION\n",
    "</pre>\n",
    "</div>\n",
    "</div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "<div class=\"cell border-box-sizing text_cell rendered\"><div class=\"prompt input_prompt\">\n",
    "</div><div class=\"inner_cell\">\n",
    "<div class=\"\">\n",
    "<pre>\n",
    "# BEGIN TESTS\n",
    "</pre>\n",
    "</div>\n",
    "</div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sieve(1) == set()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sieve(2) == {2}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sieve(3) == {2, 3}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# HIDDEN\n",
    "sieve(20) == {2, 3, 5, 7, 11, 13, 17, 19}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\"\"\" # BEGIN TEST CONFIG\n",
    "points: 1\n",
    "hidden: true\n",
    "\"\"\" # END TEST CONFIG\n",
    "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}"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "<div class=\"cell border-box-sizing text_cell rendered\"><div class=\"prompt input_prompt\">\n",
    "</div><div class=\"inner_cell\">\n",
    "<div class=\"\">\n",
    "<pre>\n",
    "# END TESTS\n",
    "</pre>\n",
    "</div>\n",
    "</div>\n",
    "</div>"
   ]
  },
  {
   "cell_type": "raw",
   "metadata": {},
   "source": [
    "<div class=\"cell border-box-sizing text_cell rendered\"><div class=\"prompt input_prompt\">\n",
    "</div><div class=\"inner_cell\">\n",
    "<div class=\"\">\n",
    "<pre>\n",
    "# END QUESTION\n",
    "</pre>\n",
    "</div>\n",
    "</div>\n",
    "</div>"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}