kofhearts's blog

By kofhearts, history, 9 years ago, In English

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

  • Vote: I like it
  • -17
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Auto comment: topic has been updated by kofhearts (previous revision, new revision, compare).

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Auto comment: topic has been updated by kofhearts (previous revision, new revision, compare).

»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Auto comment: topic has been updated by kofhearts (previous revision, new revision, compare).