{
"metadata": {
"name": "",
"signature": "sha256:328d9fc1dc064d17d174d40a6a0bc8a62c611562d163bccb1a72d55e0467e80a"
},
"nbformat": 3,
"nbformat_minor": 0,
"worksheets": [
{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The prime factors of 13195 are 5, 7, 13 and 29.\n",
"\n",
"What is the largest prime factor of the number 600851475143 ?"
]
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"primes = range(120)"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 2
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"primes = [i for i in primes if i%2 != 0]"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 4
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def num_list(num):\n",
" primes = [i for i in range(num)]\n",
" for i in primes:\n",
" yield i"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 5
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"[i for i in num_list(10)]"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 6,
"text": [
"[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"
]
}
],
"prompt_number": 6
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"[i for i in num_list(10) if i%i != 0]"
],
"language": "python",
"metadata": {},
"outputs": [
{
"ename": "ZeroDivisionError",
"evalue": "integer division or modulo by zero",
"output_type": "pyerr",
"traceback": [
"\u001b[1;31m---------------------------------------------------------------------------\u001b[0m\n\u001b[1;31mZeroDivisionError\u001b[0m Traceback (most recent call last)",
"\u001b[1;32m<ipython-input-7-354e48873b71>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[1;33m[\u001b[0m\u001b[0mi\u001b[0m \u001b[1;32mfor\u001b[0m \u001b[0mi\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mnum_list\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m10\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;32mif\u001b[0m \u001b[0mi\u001b[0m\u001b[1;33m%\u001b[0m\u001b[0mi\u001b[0m \u001b[1;33m!=\u001b[0m \u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
"\u001b[1;31mZeroDivisionError\u001b[0m: integer division or modulo by zero"
]
}
],
"prompt_number": 7
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"primes = range(2, 10)\n",
"\n",
"while primes:\n",
" x = primes.pop(0)\n",
" print x, primes\n",
" primes = [i for i in primes if i%x != 0]"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"2 [3, 4, 5, 6, 7, 8, 9]\n",
"3 [5, 7, 9]\n",
"5 [7]\n",
"7 []\n"
]
}
],
"prompt_number": 8
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def prime_list(num):\n",
" primes = range(2, num)\n",
"\n",
" while primes:\n",
" x = primes.pop(0)\n",
" yield x\n",
" primes = [i for i in primes if i%x != 0]"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 9
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"[ i for i in prime_list(10)]"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 11,
"text": [
"[2, 3, 5, 7]"
]
}
],
"prompt_number": 11
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"%%time\n",
"max([i for i in prime_list(100000) if 600851475143%i == 0])"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"CPU times: user 6.34 s, sys: 7.58 ms, total: 6.35 s\n",
"Wall time: 6.35 s\n"
]
},
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 13,
"text": [
"6857"
]
}
],
"prompt_number": 13
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"600851475143/6857"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 14,
"text": [
"87625999"
]
}
],
"prompt_number": 14
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"%%time\n",
"max([i for i in prime_list(100000) if 87625999%i == 0])"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"CPU times: user 6.45 s, sys: 18.6 ms, total: 6.47 s\n",
"Wall time: 6.46 s\n"
]
},
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 15,
"text": [
"1471"
]
}
],
"prompt_number": 15
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"87625999/1471"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 17,
"text": [
"59569"
]
}
],
"prompt_number": 17
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"%%time\n",
"max([i for i in prime_list(100000) if 59569%i == 0])"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"CPU times: user 5.84 s, sys: 36.8 ms, total: 5.88 s\n",
"Wall time: 5.84 s\n"
]
},
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 18,
"text": [
"839"
]
}
],
"prompt_number": 18
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"plist = [i for i in prime_list(6856)]"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 35
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"poss = [i for i in plist if 600851475143%i == 0]\n",
"print poss"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"[71, 839, 1471]\n"
]
}
],
"prompt_number": 36
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"for j in poss:\n",
" maybe_prime = (600851475143/j)\n",
" print j, maybe_prime, [i for i in plist if maybe_prime%i == 0]"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"71 8462696833 [839, 1471]\n",
"839 716151937 [71, 1471]\n",
"1471 408464633 [71, 839]\n"
]
}
],
"prompt_number": 37
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"poss = [i for i in plist if 408464633%i == 0]\n",
"print poss\n",
"\n",
"for j in poss:\n",
" maybe_prime = (408464633/j)\n",
" print j, maybe_prime, [i for i in plist if maybe_prime%i == 0]"
],
"language": "python",
"metadata": {},
"outputs": [
{
"output_type": "stream",
"stream": "stdout",
"text": [
"[71, 839]\n",
"71 5753023 [839]\n",
"839 486847 [71]\n"
]
}
],
"prompt_number": 38
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"def max_prime(num, guess): \n",
" primes = prime_list(guess)\n",
" factors = [i for i in primes if num%i == 0]\n",
" \n",
" \n",
" if num/reduce(lambda x, y: x*y, factors) < guess:\n",
" return max(factors)\n",
" else:\n",
" raise ValueError(\"Guess too small\")"
],
"language": "python",
"metadata": {},
"outputs": [],
"prompt_number": 49
},
{
"cell_type": "code",
"collapsed": false,
"input": [
"max_prime(600851475143, 100000)"
],
"language": "python",
"metadata": {},
"outputs": [
{
"metadata": {},
"output_type": "pyout",
"prompt_number": 50,
"text": [
"6857"
]
}
],
"prompt_number": 50
},
{
"cell_type": "code",
"collapsed": false,
"input": [],
"language": "python",
"metadata": {},
"outputs": []
}
],
"metadata": {}
}
]
}