HW_Primes_I_CW.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "HW_Primes I_CW",
      "provenance": [],
      "collapsed_sections": [],
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/cw805/MATH-242/blob/main/HW_Primes_I_CW.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "1sz37RJiHzE2"
      },
      "source": [
        "# Primes I Practice Problems\n",
        "\n",
        "**Learning Goals:** Gain proficiency with Python coding. Explore simple patterns in prime numbers.\n",
        "\n",
        "**Your task:** Complete the two practice problems below. Type your solutions in code cells below each problem.\n",
        "\n",
        "**Due:** Friday, April 8, at 5:00pm. Do the following to submit your work.\n",
        "\n",
        "1. Click on *Share* in the upper right corner of this window. Make sure your notebook is viewable by Prof. Wright and the course grader(s).\n",
        "2. In the *Get link*, click *Copy link*.\n",
        "3. Go to the [Primes I](https://mdl.stolaf.edu/mod/assign/view.php?id=189237) assignment on Moodle. Paste the link to your notebook in the text field for the assignment submission. This will allow Prof. Wright or either of the course graders to view your Colab notebook.\n",
        "\n",
        "**Grading:** Each exercise will be graded on a Satisfactory/Unsatisfactory scale. If you use Python code to correctly find the answer to each question, you will receive a Satisfactory grade for that exercise.\n",
        "\n",
        "**Need help?** Review the notes from class and Python documentation links on the course web site. If you still need help, email Prof. Wright. Don't forget there are also evening help sessions &mdash; the help session schedule is at the top of the course website.\n"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Problem 1: Twin Primes\n",
        "\n",
        "Primes that differ by exactly $2$ are called **twin primes**. If $p$ and $p+2$ are both prime, then $(p, p+2)$ is a **twin prime pair**. For example, $(11, 13)$ is a twin prime pair, as is $(29, 31)$.\n",
        "\n",
        "Write some code to find twin primes. As a starting point, you may use a sieve method from class to produce a list of primes.\n",
        "\n",
        "**Then aswer the question: *How many twin prime pairs are less than 10,000?***"
      ],
      "metadata": {
        "id": "N7X8PLavhIq9"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "import math"
      ],
      "metadata": {
        "id": "XF9zIqLcaFOc"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "def countTwinPrime(nMax):\n",
        "     \n",
        "    prime = [True for i in range(nMax + 2)]\n",
        "    p = 2\n",
        "    pairs = 0\n",
        "     \n",
        "    while (p * p <= nMax + 1):         \n",
        "        if (prime[p] == True):            \n",
        "            for i in range(2 * p, nMax + 2, p):\n",
        "                prime[i] = False\n",
        "        p += 1\n",
        "\n",
        "    for p in range(2, nMax - 1):\n",
        "        if prime[p] and prime[p + 2]:\n",
        "          pairs += 1\n",
        "    \n",
        "    \n",
        "    return pairs\n",
        "  "
      ],
      "metadata": {
        "id": "VureRNP0iKzc"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "countTwinPrime(10000)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "UFrKWGXp9E7u",
        "outputId": "481f8930-cf92-454e-8159-8cb4d94e108c"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "205"
            ]
          },
          "metadata": {},
          "execution_count": 3
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "## Problem 2: Prime Gaps\n",
        "\n",
        "A **prime gap** is the difference between two successive primes. For example, $13$ and $17$ are successive primes (i.e., there are no primes between them) with a gap of $4$.\n",
        "\n",
        "Write some code to compute prime gaps. As a starting point, you may use a sieve method from class to produce a list of primes.\n",
        "\n",
        "**Then aswer the question: *What are the smallest two successive primes with a gap of at least 100?***"
      ],
      "metadata": {
        "id": "QeFbzl-niL_G"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "# First find list of prime \n",
        "\n",
        "def fastEratos(nMax):\n",
        "\n",
        "  nums = list(range(2,nMax+1)) \n",
        "  nroot = math.sqrt(nMax)\n",
        "\n",
        "  i = 0 # index of smallest item in nums\n",
        "  while nums[i] <= nroot:\n",
        "\n",
        "    if nums[i] > 0:   # then nums[i] is prime, so set all of its multiples to zero\n",
        "      j = i + nums[i] # this index of twice the prime nums[i]\n",
        "      while j < len(nums):\n",
        "        nums[j] = 0\n",
        "        j += nums[i]    # go to the next multiple of the prime nums[i]\n",
        "\n",
        "    i += 1 \n",
        "\n",
        " \n",
        "  primes = [n for n in nums if n != 0]\n",
        "  return primes"
      ],
      "metadata": {
        "id": "qzb7kTl7C9uO"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "fastEratos(50)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "Ot5zYNaHC_hs",
        "outputId": "1d47add3-833b-4d48-f5cd-8c0ddd341861"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]"
            ]
          },
          "metadata": {},
          "execution_count": 7
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "# Goal: find smallest two successive primes with a gap of at least 100\n",
        "# find first successive prime as p (primeList[i]?), then successive = primeList[i + 1]\n",
        "# primeList[i + 1] - primeList[i]\n",
        "\n",
        "def primeGap(nMax,minGap):\n",
        " \n",
        "  primeList = fastEratos(nMax)\n",
        "\n",
        "  for i in range(len(primeList)):\n",
        "    first = primeList[i]\n",
        "    second = primeList[i + 1]\n",
        "    gap = second - first    \n",
        "    if gap >= minGap:\n",
        "      return first,second "
      ],
      "metadata": {
        "id": "-XUEHKX1iMM7"
      },
      "execution_count": null,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "# test the function\n",
        "primeGap(10000000,100)"
      ],
      "metadata": {
        "id": "G0drE_7t_-aA",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "8847a7e7-d189-479b-afd1-0afa1870fca6"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "(370261, 370373)"
            ]
          },
          "metadata": {},
          "execution_count": 22
        }
      ]
    }
  ]
}