Нахождение простых множителей числа с помощью «для цикла» в Python - PullRequest
Новая
       10

Нахождение простых множителей числа с помощью «для цикла» в Python

0 голосов
/ 02 июня 2018

Я знаю, как реализовать это, используя цикл while, но мне нужно найти решение, используя цикл for.Для данного числа = 56 мой код ниже выводит [2, 7, 4], тогда как правильный ответ будет [2,2,2,7].куда я иду не так? 

def prime_fac(num):
    a = num
    pf = []
    for x in range(2,a):
        if a % x == 0:
            if x == 2 or x == 3:
                pf.append(x)
                a = a//x
            else:
                for y in range(2,x):
                    if (x % y) == 0:
                        break
                else:
                    pf.append(x)
                    a = a // x
        else:
            continue
    if a>1:
        pf.append(a)
    print (f"Prime factors of {num} are {pf}")
number = int(input('Enter a number to find its prime factors: '))
prime_fac(number)

1 Ответ

0 голосов
/ 02 июня 2018

Ваша проблема в алгоритме, а не в коде Python.Ваша программа увеличивает делитель x, когда она делит a, без проверки, если x**i (i> 1) делит a.В ваших выходных данных последнее число представляет собой произведение всех простых чисел, которые более одного раза являются делителем a.Вы можете использовать отладчики, такие как PythonTutor , чтобы выяснить, где ваша программа не выполняет то, что вы ожидаете.

На самом деле, я просто хотел дать вам псевдокод для улучшения вашего алгоритма, чтобы вы могли реализовать алгоритм.Но потом я заметил, что в Python псевдокод был почти таким же: 

def prime_fac(num):
    a = num
    pf = []
    #ranges in Python don't include the last element, therefore we need a + 1 to detect also prime numbers
    for x in range(2, a + 1):
        #check if x is divisor and repeat
        while a % x == 0:
            pf.append(x)
            a = a // x

        #all factors found?
        if a == 1:
            #yes, return list with prime factors
            return pf 
        #no, go to next x

И теперь вы можете попытаться повысить эффективность вашего алгоритма, потому что эта стратегия довольно медленная.

...