{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "Let \$p_i = {2, 3, 4, 5, \\dots}\$ we continue to divide \$c\$ by \$p_i\$. If \$c\$ becomes 1 then \$p_i\$ is the greatest prime factor, otherwise we increase \$p_i\$ by one. We know that any \$p_i\$ that divides \$c\$ is prime, because otherwise it would be of the form \$p_i = {q_1}^{a_i} \\dotsm {q_n}^{a_n}\$ and since \$q_i\$ is smaller than \$p_i\$, \$c\$ would have been already divided by it, so \$p_i\$ must be a prime number. " ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "6857" ] }, "execution_count": 1, "metadata": {}, "output_type": "execute_result" } ], "source": [ "c = 600851475143\n", "p = 2\n", "while c > 1:\n", " if c % p == 0:\n", " c /= p\n", " continue\n", " p += 1\n", "p" ] } ], "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.7.4" }, "title": "Largest prime factor" }, "nbformat": 4, "nbformat_minor": 4 }