Способ выражения простых коэффициентов числа

Question

Моя задача - вернуть простые множители целого числа (n). Мой вопрос: как выразить это в математическом выражении для кодирования? Я знаю, что простые числа - это числа, которые делятся только на 1 и сами, но не знают, как это сделать в коде.

Я тем не менее найти эту кодировку, которая работает, но я не знаю, почему:

def primes(n): 

    primfac = [] 
    d = 2 
    while d*d <= n: 
     while (n % d) == 0: 
      primfac.append(d) 
      n //= d 
     d += 1 
    if n > 1: 
     primfac.append(n) 
    return primfac 

Может кто-нибудь объяснить мне, почему это кодирование работает? Почему d выбран как 2, чтобы начать вместо 1? Также почему он равен d и проверяет, равен ли он или меньше n? и так далее.

Answer 1

d Начинается с 2, потому что вы получите бесконечный список из 1s в качестве факторов, как Tom Karzes. Причина в том, что он квадрат d и проверяет, равен ли он n, потому что вам нужно только проверить квадратный корень из числа его коэффициентов, а math.sqrt() является более вычислительно дорогим, чем квадрат. Что он делает, так это проверяет, d us в n до d достигает квадратного корня n. Затем он добавляет d, потому что он был проверен как фактор.

Есть ли что-нибудь еще, что вы не поняли о коде?