{
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": "## Writing C in Python with Cython"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": "### Installing Cython and a C compiler for Python"
    },
    {
      "cell_type": "markdown",
      "metadata": {},
      "source": "### Implementing the Eratosthenes Sieve in Python and Cython"
    },
    {
      "cell_type": "code",
      "execution_count": 1,
      "metadata": {},
      "outputs": [],
      "source": "def primes_python(n):\n    primes = [False, False] + [True] * (n - 2)\n    i = 2\n    while i < n:\n        # We do not deal with composite numbers.\n        if not primes[i]:\n            i += 1\n            continue\n        k = i * i\n        # We mark multiples of i as composite numbers.\n        while k < n:\n            primes[k] = False\n            k += i\n        i += 1\n    # We return all numbers marked with True.\n    return [i for i in range(2, n) if primes[i]]"
    },
    {
      "cell_type": "code",
      "execution_count": 2,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": "[2, 3, 5, 7, 11, 13, 17, 19]"
          },
          "execution_count": 2,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": "primes_python(20)"
    },
    {
      "cell_type": "code",
      "execution_count": 3,
      "metadata": {},
      "outputs": [],
      "source": "n = 10000"
    },
    {
      "cell_type": "code",
      "execution_count": 4,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": "100 loops, best of 3: 4 ms per loop"
          },
          "execution_count": 4,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": "%timeit primes_python(n)"
    },
    {
      "cell_type": "code",
      "execution_count": 5,
      "metadata": {},
      "outputs": [],
      "source": "%load_ext Cython"
    },
    {
      "cell_type": "code",
      "execution_count": 6,
      "metadata": {
        "scrolled": true
      },
      "outputs": [],
      "source": "%%cython\ndef primes_cython_1(n):\n    primes = [False, False] + [True] * (n - 2)\n    i = 2\n    while i < n:\n        # We do not deal with composite numbers.\n        if not primes[i]:\n            i += 1\n            continue\n        k = i * i\n        # We mark multiples of i as composite numbers.\n        while k < n:\n            primes[k] = False\n            k += i\n        i += 1\n    # We return all numbers marked with True.\n    return [i for i in range(2, n) if primes[i]]"
    },
    {
      "cell_type": "code",
      "execution_count": 7,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": "[2, 3, 5, 7, 11, 13, 17, 19]"
          },
          "execution_count": 7,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": "primes_cython_1(20)"
    },
    {
      "cell_type": "code",
      "execution_count": 8,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": "100 loops, best of 3: 1.99 ms per loop"
          },
          "execution_count": 8,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": "%timeit primes_cython_1(n)"
    },
    {
      "cell_type": "code",
      "execution_count": 9,
      "metadata": {},
      "outputs": [],
      "source": "%%cython -a\ndef primes_cython_2(int n):\n    # Note the type declarations below:\n    cdef list primes = [False, False] + [True] * (n - 2)\n    cdef int i = 2\n    cdef int k = 0\n    # The rest of the function is unchanged.\n    while i < n:\n        # We do not deal with composite numbers.\n        if not primes[i]:\n            i += 1\n            continue\n        k = i * i\n        # We mark multiples of i as composite numbers.\n        while k < n:\n            primes[k] = False\n            k += i\n        i += 1\n    # We return all numbers marked with True.\n    return [i for i in range(2, n) if primes[i]]"
    },
    {
      "cell_type": "code",
      "execution_count": 10,
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": "1000 loops, best of 3: 266 \u00b5s per loop"
          },
          "execution_count": 10,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": "%timeit primes_cython_2(n)"
    }
  ],
  "metadata": {},
  "nbformat": 4,
  "nbformat_minor": 0
}