Mathematics/Euler_Totient_SingleNum.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Euler_Totient_SingleNum.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "metadata": {
        "id": "a3hYgaHPUkua"
      },
      "source": [
        "'''\n",
        "  Function to find the number of coprimes less than n based on Euler totient function\n",
        "  Time complexity = O(sqrt(n) + k); \n",
        "    n is the input number\n",
        "    k is the number of prime factors of n\n",
        "\n",
        "  Parameters:\n",
        "  -----------\n",
        "    n: integer\n",
        "       The input positive number  \n",
        "\n",
        "  Returns:\n",
        "  --------\n",
        "    phi: integer\n",
        "         Phi value of n (the number of coprimes < n)\n",
        "\n",
        "  Examples:\n",
        "  ---------\n",
        "    >>> n_cp = Euler_Totient_SingleNum(11)\n",
        "    >>> print(n_cp) \n",
        "    10\n",
        "\n",
        "  See also:\n",
        "    https://github.com/leduckhai/Awesome-Competitive-Programming/blob/main/Mathematics/Euler_Totient_NumList.ipynb    \n",
        "\n",
        "  Reference: \n",
        "    https://en.wikipedia.org/wiki/Euler%27s_totient_function#Euler's_product_formula\n",
        "    https://cp-algorithms.com/algebra/phi-function.html\n",
        "'''\n",
        "\n",
        "def Euler_Totient_SingleNum(n):\n",
        "  '''\n",
        "    Function to find all prime factors of a positive integer\n",
        "    Time complexity = O(sqrt(n))\n",
        "\n",
        "    See also:\n",
        "      https://github.com/leduckhai/Awesome-Competitive-Programming/blob/main/Mathematics/PrimeFactorization.ipynb\n",
        "  '''\n",
        "\n",
        "  def PrimeFactorization(n):\n",
        "    factors = []\n",
        "    d = 2\n",
        "\n",
        "    while n > 1:\n",
        "      \n",
        "      while n % d == 0:\n",
        "        if d not in factors:\n",
        "          factors.append(d)\n",
        "        n /= d\n",
        "\n",
        "      d += 1\n",
        "\n",
        "      if d*d > n:\n",
        "        if n > 1: \n",
        "          factors.append(int(n))\n",
        "          break\n",
        "\n",
        "    return factors\n",
        "\n",
        "  # Core function\n",
        "  PFs = PrimeFactorization(n) # All prime factors of n\n",
        "  phi = n \n",
        "\n",
        "  for p in PFs:\n",
        "    phi *= (1-1/p)\n",
        "\n",
        "  return int(phi)"
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}