{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Use the Sieve of Eratosthenes to generate prime numbers\n",
    "\n",
    "https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes\n",
    "\n",
    "This is code I found when looking for code to profile that someone had written. It gets the right answer but takes several minutes for the 1st million primes, you should be able to do much better."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Code worked\n",
      "\n",
      "Profile the code:\n",
      "\n",
      "         18776 function calls in 1.172 seconds\n",
      "\n",
      "   Ordered by: standard name\n",
      "\n",
      "   ncalls  tottime  percall  cumtime  percall filename:lineno(function)\n",
      "    10000    0.031    0.000    0.031    0.000 :0(append)\n",
      "        1    0.000    0.000    1.172    1.172 :0(exec)\n",
      "     8771    0.344    0.000    0.344    0.000 :0(remove)\n",
      "        1    0.000    0.000    0.000    0.000 :0(setprofile)\n",
      "        1    0.797    0.797    1.172    1.172 <ipython-input-10-37941588efc4>:1(slowPrimeDigits)\n",
      "        1    0.000    0.000    1.172    1.172 <string>:1(<module>)\n",
      "        1    0.000    0.000    1.172    1.172 profile:0(out = slowPrimeDigits(10000))\n",
      "        0    0.000             0.000          profile:0(profiler)\n",
      "\n",
      "\n",
      "Note the append and must mostly remove functions are taking a lot of time...\n"
     ]
    }
   ],
   "source": [
    "def slowPrimeDigits(maxValue):\n",
    "    \"\"\" Very slow way to make a list of primes\n",
    "    Start a list, then remove each number that is a prime times n\n",
    "    \"\"\"\n",
    "    # make an array to hold each number up to maxValue\n",
    "    primes = []\n",
    "    # fill the array\n",
    "    for i in range(maxValue):\n",
    "        primes.append(i)\n",
    "    # zero and one are not prime\n",
    "    primes.remove(0)\n",
    "    primes.remove(1)\n",
    "    # now apply Sieve of Eratosthenes (google it...)\n",
    "    for i in primes:\n",
    "        # make a list of all factors of i (next prime)\n",
    "        factors = range(i, maxValue, i)\n",
    "        # first factor is prime (it stays) the rest are removed\n",
    "        for f in factors[1:]:\n",
    "            # check if f is still in primes\n",
    "            if f in primes:\n",
    "                # if so remove from \n",
    "                primes.remove(f)\n",
    "    # output\n",
    "    return primes\n",
    "\n",
    "# set maxmimum value\n",
    "# for the \"slow\" code only do up to 10k \n",
    "max10k = 10000\n",
    "sumOfPrimes10k = 5736396\n",
    "\n",
    "# for fast code can do up to 1M \n",
    "max1M = 1000000\n",
    "sumOfPrimes1M = 37550402023\n",
    "\n",
    "\n",
    "# timeit runs repeated loops on a line to check how fast it is\n",
    "# check output is what we expect...\n",
    "\n",
    "# test new code with\n",
    "import numpy\n",
    "if(numpy.sum(slowPrimeDigits(max10k)) != sumOfPrimes10k): \n",
    "    print('\\nCode failed')\n",
    "else:\n",
    "    print('\\nCode worked')\n",
    "    \n",
    "import profile\n",
    "print(\"\\nProfile the code:\\n\")\n",
    "profile.run('out = slowPrimeDigits({})'.format(max10k))\n",
    "\n",
    "print(\"Note the append and must mostly \\'remove\\' functions are taking a lot of time...\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1 loop, best of 3: 1.01 s per loop\n"
     ]
    }
   ],
   "source": [
    "# use the built in \"magic\" timeit command to test the function over several attempts\n",
    "timeit if(numpy.sum(slowPrimeDigits(max10k)) != sumOfPrimes10k): print('Code failed')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.6.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}