understanding factorization method. help!

Revision en1, by kofhearts, 2015-12-18 11:50:31

hello codeforces,

I am trying to understand the reason why only up to sqrt of n numbers are checked for factors. There is a maths theorem that if a number is not prime then it should have at least 1 factor which is less than sqrt(n). Is the following routine using that fact. My understanding is that in each iteration it is trying to find at least 1 such factor less than sqrt of n and once it finds it then the new n is updated to n / factor. This will give a new n and the same procedure is applied i.e another small factor is tried to be found in the range till sqrt of n. Please give me a better explanation if there is an easier way to understand why we just need to search till sqrt(n) for the factors. I appreciate it! Thanks!


def primes(n): primfac = [] d = 2 while d*d <= n: while (n % d) == 0: primfac.append(d) # supposing you want multiple factors repeated n //= d d += 1 if n > 1: primfac.append(n) return primfac
Tags factorisation

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English kofhearts 2015-12-18 11:50:31 1072 Initial revision (published)