Prime Factorization of a Number in Python and why we check upto the square root of the Number

Why we go upto sqrt(n)​ for finding all Prime factorization of a number

p <= sqrt(n} or q <= sqrt(n)
while number % prime_num == 0:
prime_factors.append(int(prime_num))
number /= prime_num

The Algorithm / Steps

number /= prime_num

In prime factorization of n the loop goes upto square root of n and not till n.

DataScience | ML | 2x Kaggle Expert. Ex Fullstack Engineer and Ex International Financial Analyst. https://www.linkedin.com/in/rohan-paul-b27285129/

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store