euler-003-largest-prime-factor-20150227.ipynb

{
 "metadata": {
  "name": "euler-003-largest-prime-factor-20150227"
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "!factor 600851475143 | rev | awk '{print $1}' | rev"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "6857\r\n"
       ]
      }
     ],
     "prompt_number": 1
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "!factor 600851475143 | awk '{print $NF}'"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "6857\r\n"
       ]
      }
     ],
     "prompt_number": 2
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "import math\n",
      "\n",
      "def get_factors(x):\n",
      "    '''Returns of prime factors of x in ascending order.'''\n",
      "    factors = []\n",
      "    factor = 2\n",
      "    while factor <= math.sqrt(x):\n",
      "        while x % factor == 0:\n",
      "            factors.append(factor)\n",
      "            x /= factor\n",
      "        factor += 1\n",
      "    if x != 1:\n",
      "        factors.append(x)\n",
      "    return factors"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 3
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "n = 600851475143"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 4
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "get_factors(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 5,
       "text": [
        "[71, 839, 1471, 6857L]"
       ]
      }
     ],
     "prompt_number": 5
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def foo(x):\n",
      "    return get_factors(x)[-1]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 6
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1000 loops, best of 3: 1.34 ms per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 7,
       "text": [
        "6857L"
       ]
      }
     ],
     "prompt_number": 7
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def get_factors(x):\n",
      "    '''Returns of prime factors of x in ascending order.'''\n",
      "    factors = []\n",
      "    factor = 2\n",
      "    while factor * factor <= x:\n",
      "        while x % factor == 0:\n",
      "            factors.append(factor)\n",
      "            x /= factor\n",
      "        factor += 1\n",
      "    if x != 1:\n",
      "        factors.append(x)\n",
      "    return factors"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 8
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1000 loops, best of 3: 973 us per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 9,
       "text": [
        "6857L"
       ]
      }
     ],
     "prompt_number": 9
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "get_factors(1000)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 10,
       "text": [
        "[2, 2, 2, 5, 5, 5]"
       ]
      }
     ],
     "prompt_number": 10
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "get_factors(600851475143)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 11,
       "text": [
        "[71, 839, 1471, 6857L]"
       ]
      }
     ],
     "prompt_number": 11
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "get_factors(600851475143)[-1]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "pyout",
       "prompt_number": 12,
       "text": [
        "6857L"
       ]
      }
     ],
     "prompt_number": 12
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def get_factors(x):\n",
      "    '''Returns of prime factors of x in ascending order.'''\n",
      "    factors = []\n",
      "    factor = 2\n",
      "    while factor * factor <= x:\n",
      "        while x % factor == 0:\n",
      "            factors.append(factor)\n",
      "            x /= factor\n",
      "        factor += 1\n",
      "    if x != 1:\n",
      "        factors.append(x)\n",
      "    return factors"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 13
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from euler import get_factors2\n",
      "get_factors = get_factors2"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 14
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "10000 loops, best of 3: 188 us per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 15,
       "text": [
        "6857L"
       ]
      }
     ],
     "prompt_number": 15
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from euler import get_factors3\n",
      "get_factors = get_factors3"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 16
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1000 loops, best of 3: 229 us per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 17,
       "text": [
        "6857L"
       ]
      }
     ],
     "prompt_number": 17
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from euler import get_factors4\n",
      "get_factors = get_factors4"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 18
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1000000 loops, best of 3: 661 ns per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 19,
       "text": [
        "6857L"
       ]
      }
     ],
     "prompt_number": 19
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from euler import get_factors"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 20
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1000000 loops, best of 3: 661 ns per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 21,
       "text": [
        "6857L"
       ]
      }
     ],
     "prompt_number": 21
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from euler import get_factors5\n",
      "get_factors = get_factors5"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 22
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1000000 loops, best of 3: 661 ns per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 23,
       "text": [
        "6857L"
       ]
      }
     ],
     "prompt_number": 23
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from euler import canonical_decomposition2\n",
      "foo = canonical_decomposition2\n",
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "10000 loops, best of 3: 197 us per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 24,
       "text": [
        "{71: 1, 839: 1, 1471: 1, 6857L: 1}"
       ]
      }
     ],
     "prompt_number": 24
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from euler import canonical_decomposition3\n",
      "foo = canonical_decomposition3\n",
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "10000 loops, best of 3: 192 us per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 25,
       "text": [
        "{71: 1, 839: 1, 1471: 1, 6857L: 1}"
       ]
      }
     ],
     "prompt_number": 25
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from euler import canonical_decomposition4\n",
      "foo = canonical_decomposition4\n",
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "10000 loops, best of 3: 197 us per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 26,
       "text": [
        "Counter({6857L: 1, 839: 1, 1471: 1, 71: 1})"
       ]
      }
     ],
     "prompt_number": 26
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from euler import canonical_decomposition5\n",
      "foo = canonical_decomposition5\n",
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1000 loops, best of 3: 235 us per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 27,
       "text": [
        "Counter({6857L: 1, 839: 1, 1471: 1, 71: 1})"
       ]
      }
     ],
     "prompt_number": 27
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "from euler import canonical_decomposition\n",
      "foo = canonical_decomposition\n",
      "%timeit foo(n)\n",
      "foo(n)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "1000 loops, best of 3: 230 us per loop\n"
       ]
      },
      {
       "output_type": "pyout",
       "prompt_number": 28,
       "text": [
        "{71: 1, 839: 1, 1471: 1, 6857L: 1}"
       ]
      }
     ],
     "prompt_number": 28
    }
   ],
   "metadata": {}
  }
 ]
}