Mathematics/Sieve_SPF.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "asdf.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "code",
      "metadata": {
        "id": "a3hYgaHPUkua"
      },
      "source": [
        "'''\n",
        "  Function to find SPF (Smallest Prime Factor) for all numbers < N\n",
        "  Time complexity = O(nloglogn) \n",
        "  \n",
        "  Parameters:\n",
        "    N: integer\n",
        "\n",
        "  Returns:\n",
        "    SPFs: list\n",
        "          All Smallest Prime Factors of all numbers from 0 to N-1\n",
        "\n",
        "  Examples:\n",
        "    >>> SPFs = Sieve_SPF(10)\n",
        "    >>> print(SPFs)\n",
        "    [0, 1, 2, 3, 2, 5, 2, 7, 2, 3]\n",
        "\n",
        "  See also:\n",
        "    https://github.com/leduckhai/Awesome-Competitive-Programming/blob/main/Mathematics/PrimeFactorization_SPF.ipynb\n",
        "    \n",
        "  References: \n",
        "    https://www.geeksforgeeks.org/prime-factorization-using-sieve-olog-n-multiple-queries/\n",
        "'''\n",
        "\n",
        "from math import ceil, sqrt\n",
        "\n",
        "def Sieve_SPF(N):\n",
        "  # Stores smallest prime factor for every number\n",
        "  SPFs = [0]*N\n",
        "  SPFs[1] = 1\n",
        "\n",
        "  for i in range(2, N):\n",
        "    # Mark smallest prime factor for every number to be itself\n",
        "    SPFs[i] = i\n",
        "\n",
        "  # Separately marking spf for every even number as 2\n",
        "  for i in range(4, N, 2):\n",
        "    SPFs[i] = 2\n",
        "\n",
        "  for i in range(3, ceil(sqrt(N))):\n",
        "    # Check if i is prime\n",
        "    if (SPFs[i] == i):\n",
        "      # Mark SPFs for all numbers divisible by i\n",
        "      for j in range(i * i, N, i):\n",
        "        # Mark SPFs[j] if it is not previously marked\n",
        "        if (SPFs[j] == j):\n",
        "          SPFs[j] = i \n",
        "\n",
        "  return SPFs"
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}