euler-005-smallest-multiple-20130725.ipynb

{
 "metadata": {
  "name": "euler-005-smallest-multiple-20130725"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from euler import get_factors"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "get_factors(20)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 2,
       "text": [
        "[2, 2, 5]"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def terse(x):\n",
      "    f = {}\n",
      "    for i in x:\n",
      "        if i not in f:\n",
      "            f[i] = 0\n",
      "        f[i] += 1\n",
      "    return f"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "terse(get_factors(20))"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 4,
       "text": [
        "{2: 2, 5: 1}"
       ]
      }
     ],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def get_terse_primes(x):\n",
      "    primes = {}\n",
      "    for i in range(2, x + 1):\n",
      "        p = terse(get_factors(i))\n",
      "        for key in p:\n",
      "            if key not in primes:\n",
      "                primes[key] = 0\n",
      "            if p[key] > primes[key]:\n",
      "                primes[key] = p[key]\n",
      "    return primes"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 5
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "get_terse_primes(20)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 6,
       "text": [
        "{2: 4, 3: 2, 5: 1, 7: 1, 11: 1, 13: 1, 17: 1, 19: 1}"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def product_terse_primes(x):\n",
      "    product = 1\n",
      "    primes = get_terse_primes(x)\n",
      "    for prime in primes:\n",
      "        product *= prime ** primes[prime]\n",
      "    return product"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 7
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%timeit product_terse_primes(20)\n",
      "product_terse_primes(20)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "10000 loops, best of 3: 77.8 us per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 8,
       "text": [
        "232792560"
       ]
      }
     ],
     "prompt_number": 8
    }
   ],
   "metadata": {}
  }
 ]
}