PrimeFactor_Why_Check_Upto_SquareRoot.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Why we go upto sqrt(n)​ for finding all Prime factorization of a number\n",
    "\n",
    "#### First here is the Python Code"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "'''Write a function to find out the prime factors of a number. Example: prime factors of 84 -\n",
    "[2, 2, 3, 7]'''\n",
    "\n",
    "import math\n",
    "\n",
    "\n",
    "def get_prime_factors(number):\n",
    "    prime_factors = []\n",
    "    prime_num = 2\n",
    "\n",
    "    while prime_num <= math.sqrt(number):\n",
    "        while number % prime_num == 0:\n",
    "            prime_factors.append(int(prime_num))\n",
    "            number /= prime_num\n",
    "\n",
    "        prime_num += 1\n",
    "\n",
    "    if number > 1:\n",
    "        prime_factors.append(int(number))\n",
    "\n",
    "    return prime_factors\n",
    "\n",
    "\n",
    "print(get_prime_factors(84))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To understand the above first note these two mathmatical conjectures for Prime Factorization of any number\n",
    "\n",
    "1st conjecture\n",
    "\n",
    "> **If n is not a prime number AT-LEAST one Prime factor would be less than √n**\n",
    "\n",
    "**Proof:**\n",
    "\n",
    "Suppose _n_ is a positive integer such that n=pq, where _p_ and _q_ are prime numbers. Assume p > sqrt(n) and q > sqrt(n)​. Multiplying these inequalities we have p*q > sqrt(n)*sqrt(n) >​, which implies p*q >n. This is a contradiction to our hypothesis n=pq. Hence we can conclude that either\n",
    "\n",
    "p <= sqrt(n} or q <= sqrt(n)\n",
    "\n",
    "And the second conjecture\n",
    "\n",
    "> **If n is not a prime number — There can be AT-MOST 1 prime factor of n greater than sqrt(n).**\n",
    "\n",
    "**Proof :**\n",
    "\n",
    "If possible let there exists two greater sqrt(n) then their product should also divide n but which will exceed n, which contradicts our assumption. So there can NOT be more than 1 prime factor of n greater than sqrt(n).\n",
    "\n",
    "And the above is so important in Prime Factorization of a number — So, in my above code when I want to get all the prime factors of n then I need at most check for Primality upto sqrt(n). And after checking upto sqrt(n) — the number left-over after dividing n with all possible powers of primes less than sqrt(n) is EITHER a prime or 1.\n",
    "\n",
    "Note I am taking care of **“all possible powers of primes”** in the above code with the below portion inside the first while loop -\n",
    "\n",
    "\n",
    "Meaning as soon as I find a Prime-factor, I am adjusting / reducing the initial number by dividing it by that just discovered prime-factor.\n",
    "\n",
    "And so the second part of my algorithm should capture the left-over number to be the greater-than sqrt(n) Prime factor ONLY if that left-over number is > 1 . And if the left-over number is = 1 then just ignore it.\n",
    "\n",
    "First here the gist of the code\n",
    "\n",
    "\n",
    "#### The Algorithm / Steps\n",
    "\n",
    "1> I start the divisor to be the smallest prime number, which is 2. Divide by 2 as many times as I can, until I can no longer divide by 2. (And during this process, record the number of times I can successfully divide.)\n",
    "\n",
    "Further on why I am dividing or adjusting the initial number in the above\n",
    "\n",
    "number /= prime_num\n",
    "\n",
    "Say, if I do not divide — prime factors with greater than 1 multiplicity will result in the larger factor being non-prime. I dont want to consider about **2*n** or **3*n** because I have already checked and captured in my prime_factor list for 2 and 3\n",
    "\n",
    "So, to solve the above problem, I keep dividing the larger factor of a pair by the smaller one until it no longer divides.\n",
    "\n",
    "2> So with each successive while loop I am dividing the number by successively larger primes until I find one that is a factor of the number.\n",
    "\n",
    "That is after the first division by 2 (assuming I found 2 to be a factor of the initial number), take the result from (1) i.e. the adjusted number after dividion by 2, and divide by 3 as many times as I can.\n",
    "\n",
    "Then go to the next prime number, 5. Take the result from (2), and divide by 5 as many times as I can.\n",
    "\n",
    "And during this successive divisions, as soon as I have found a factor or divisor, p , I can replace n with m=n/p and continue the process of trial division with primes greater than or equal to p up to (n/p)¹/2\n",
    "\n",
    "Repeat the process, until final result is 1.\n",
    "\n",
    "**Now the most important part for improving time-complexity of the algorithm — which follows from the principle that -**\n",
    "\n",
    "> In prime factorization of n the loop goes upto square root of n and not till n.\n",
    "\n",
    "3> However, we don’t need to go out that far i.e. upto the number itself. If we’ve tested all the primes up to the square root of our target number without finding a divisor, we don’t need to go any further because we know that our target number is prime after all.\n",
    "\n",
    "This is because — If a number N has a prime factor larger than √n , then it surely has a prime factor smaller than √n\n",
    "\n",
    "So, it’s sufficient to search for prime factors in the range [1, sqrt(n)], and then use them in order to compute the prime factors in the range [sqrt(n), n].\n",
    "\n",
    "**The way we implement the above is as follows -**\n",
    "\n",
    "A. We know that prime factors with >1 multiplicity will result in the larger factor being non-prime. To solve this, keep dividing the larger factor of a pair by the smaller one until it no longer divides.\n",
    "\n",
    "B. As an example: For 28, factors are 2,2,7, here 7 is larger than sqroot(28), but there is no single prime number that can combine to form 28 (i.e. x*7=28, where x is prime, this does not exist, since x is 4 which is not prime), so dividing the primes from beginning with 2 multiple time will help, 28/2= 14, 14/2 = 7, then we know the 2 & 2 are prime factors, also take the remaining one 7 is also another prime number completing the prime factor list.\n",
    "\n",
    "If no prime factors exist in the range **[1, sqrt(n)]**, then “n” itself is prime and there is no need to continue searching beyond that range.\n",
    "\n",
    "To explain a little more on this — If you do not find a factor less than sqrt(n), then the number “n” itself is a prime number. Because, consider the opposite, you find two factors larger than sqrt(n), say “a” and “b”. But then a * b > sqrt(n) * sqrt(n) making their product larger than the number itself which is impossible.\n",
    "\n",
    "Therefore, if there is a factor larger than sqrt(n), there must also exist a factor smaller than sqrt(n), otherwise their product would exceed the value of “n”.\n",
    "\n",
    "But in this case it will make the variable ‘prime_num’ NON-PRIME — Because now itcan be expressed it as ( a * b ) which is only possible for NON-Prime number, as a Prime number can only be expressed as 1 * itself.\n",
    "\n",
    "But here we are ONLY interested in finding Prime factors, and so will ignore all NON-PRIME FACTORS.\n",
    "\n",
    "Hence in the above Algorithm, checking all the possible prime-number upto the **math.sqrt(number)** is sufficient.\n",
    "\n",
    "Now an important point to remember so not to get confused. - **A prime factor of a number is NOT always less than its square root -  Consider that the square root of 14 is about 3.74 but 14 has 7 as a prime factor. Also consider that any prime number such as 2 is its own (only) prime factor, and any number greater than 1 is greater than its square root**.\n",
    "\n",
    "The true Mathematical Statement is that -\n",
    "\n",
    "### The smallest prime factor of a composite number N is less than or equal to $Sqrt(N)$."
   ]
  }
 ],
 "metadata": {
  "interpreter": {
   "hash": "31f2aee4e71d21fbe5cf8b01ff0e069b9275f58929596ceb00d14d90e3e16cd6"
  },
  "kernelspec": {
   "display_name": "Python 3.8.10 64-bit",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3.8.10"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}