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