Project Euler Q3 - LO Man Hei

Download notebook

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "7f2a5876-649a-4789-b148-c21b83942c06",
   "metadata": {},
   "source": [
    "### Q3\n",
    "What is the largest prime factor of the number 600851475143 ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "5cf6759f-9608-4da1-abe6-f086689bdd0e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def prime_numbers(n):\n",
    "    result = []\n",
    "    sieve = [True] * (n+1)\n",
    "    for p in range(2, n+1):\n",
    "        if (sieve[p]):\n",
    "            result.append(p)\n",
    "            for i in range(p, n+1, p):\n",
    "                sieve[i] = False\n",
    "    return result\n",
    "\n",
    "def largest_prime_factor(n):\n",
    "    primes = prime_numbers(int(n**(1/2))+1)\n",
    "    prime_idx = 0\n",
    "    max_prime = 0\n",
    "    while n > 1 and prime_idx < len(primes):\n",
    "        if n % primes[prime_idx] != 0:\n",
    "            prime_idx += 1\n",
    "        else:\n",
    "            n //= primes[prime_idx]\n",
    "            max_prime = primes[prime_idx]\n",
    "    return max([n,max_prime])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "dfff5794-6043-4c85-a697-d6e5f92bc261",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 75 ms, sys: 0 ns, total: 75 ms\n",
      "Wall time: 73 ms\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "6857"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "largest_prime_factor(600851475143)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "ad98787e-870e-449e-9c6f-d57977251771",
   "metadata": {},
   "outputs": [],
   "source": [
    "def largest_prime_factor_2(n):   \n",
    "    i = 2\n",
    "    while i * i <= n:\n",
    "        while n%i == 0:\n",
    "            n //= i\n",
    "        if n == 1:\n",
    "            return i\n",
    "        i += 2 if i>2 else 1\n",
    "    return n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "64b347a6-4f43-4557-bd84-afc8c701ba44",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "CPU times: user 49 µs, sys: 12 µs, total: 61 µs\n",
      "Wall time: 63.7 µs\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "6857"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "%%time\n",
    "largest_prime_factor_2(600851475143)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "569318ff-58f1-4990-9320-489f6eff0071",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.8.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}

Loading