Python - целочисленная факторизация в простые числа

Question

Я написал целочисленную функцию факторизации, но, поиграв с ней, понял, что у нее проблемы с несколькими числами...

>>> pFactors(99) # it does work for numbers with multiple of one prime factor
[3, 3, 11]
>>> pFactors(999) # however, sometimes, it doesn't
[3, 37] # the actual prime factorization of 999 is [3, 3, 3, 37]. 
>>> pFactors(88)
[2, 11]
>>> pFactors(888)
[2, 3, 37]

Что не так в моем коде?

def pFactors(n):
   """Finds the prime factors of 'n'"""
   from primes import isPrime
   from math import sqrt
   pFact, limit, check, num = [], int(round(sqrt(n), 2)) + 1, 2, n
   if isPrime(n):
      return [n]
   for check in range(2, limit):
      if isPrime(check) and num % check == 0:
         pFact.append(check)
         num /= check
         if isPrime(num):
            pFact.append(num)
            break
   pFact = sorted(pFact)
   return pFact

Answer 1

Изменить так:

def pFactors(n): 
        """Finds the prime factors of 'n'""" 
        from math import sqrt 
        pFact, limit, check, num = [], int(sqrt(n)) + 1, 2, n 
        if n == 1: return [1] 
        for check in range(2, limit): 
             while num % check == 0: 
                pFact.append(check) 
                num /= check 
        if num > 1: 
          pFact.append(num) 
        return pFact 

for i in range(1,1000):
        print pFactors(i)

Хотя мне понравился твой код в том виде, в котором он был написан, несколько моментов

1. Вам не нужен isPrime. Причина в том, что любое простое число в диапазоне до предела, которое делит num, также будет наименьшим делителем любого композита, который делит num, так что, разделив эти простые числа, вы предотвратите обнаружение составных элементов, которые они составляют делители позже в диапазоне, оставляя вас только с основными факторами.

2. Вам не нужно сортировать массив, он уже отсортирован в силу check по возрастанию в порядке.

3. Добавленный цикл while обеспечивает правильный поиск повторяющихся факторов, если они продолжают делить число.

4. Вы можете использовать конгруэнции, чтобы отфильтровать 2/3 всех чисел, меньших предела, для проверки в качестве делителей. Видите ли вы, как?

Последние несколько строк приведенного выше результата:

[11, 89]
[2, 2, 5, 7, 7]
[3, 3, 109]
[2, 491]
[983]
[2, 2, 2, 3, 41]
[5, 197]
[2, 17, 29]
[3, 7, 47]
[2, 2, 13, 19]
[23, 43]
[2, 3, 3, 5, 11]
[991]
[2, 2, 2, 2, 2, 31]
[3, 331]
[2, 7, 71]
[5, 199]
[2, 2, 3, 83]
[997]
[2, 499]
[3, 3, 3, 37]

Answer 2

В примере 999 после того, как вы разделите его на 3, результат (333) также делится на 3, что дает вам 111, что вы также можете разделить на 3 (и получить 37). Но в вашем коде вы делите его только один раз - вам нужно только найти простое число, которое делит ваше текущее число, - продолжать делить на это число до тех пор, пока это станет невозможным.