При нахождении простых множителей числа одни числа работают, а другие нет

При тестировании номеров одни работают, например 48, а другие нет. Я не уверен, как лучше всего подойти к поиску всех факторов числа.

Простые множители

def find_primes(n): 
    factors = []
    i = 2
    if n == 0:
        return 0              
    if n == 1:
        return 1                
    if n >= 2:
        while n % i == 0:
            next_n = n / i
            factors.append(i)
            n = next_n 
            if n % i != 0:
                i += 1
                continue
            elif i == n:
                break
    if len(factors) == 0:
        return "{} is a prime number.\n".format(initial_n)
    else:
        return "The prime factors of {} are: {}\n".format(initial_n, factors)


n = int(input("Enter a number to find all the Prime Factors:"))
initial_n = n
print('\n')
print(find_primes(n))

Я ожидаю получить список всех факторов числа.

Цикл while остается (или никогда не используется), если i не может разделить n хотя бы один раз, независимо от того, могут ли большие значения для i.

— 28.05.2019 03:03

python primes

28.05.2019 02:48

Почему в Python есть оператор "pass"?

Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.

Некоторые методы, о которых вы не знали, что они существуют в Python

Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...

Основы Python Часть I

Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?

LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа

Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:

Оптимизация кода с помощью тернарного оператора Python

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

Советы по эффективной веб-разработке с помощью Python

Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.

110

Перейти к ответу Данный вопрос помечен как решенный

Ответы 3

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

def find_primes(n): 
    factors = []
    i = 2
    if n == 0:
        return 0
    if n == 1:
        return 1
    if n >= 2:
        while i * i <= n:
            while n % i == 0:
                factors.append(i)
                n = n // i
            i += 1
    if n > 1:
        factors.append(n)
    if len(factors) == 1:
        return "{} is a prime number.\n".format(initial_n)
    else:
        return "The prime factors of {} are: {}\n".format(initial_n, factors)


n = int(input("Enter a number to find all the Prime Factors:"))
initial_n = n
print('\n')
print(find_primes(n))

спасибо, все работает, но у меня есть пара вопросов. Почему вы использовали «пока я * я <= n» в первом выражении? Также в чем смысл окончательного оператора if, «если n > 1»

— 28.05.2019 04:00

@parth, если n - простое число, оно имеет по крайней мере один делитель, не превышающий sqrt (n), поэтому «пока i * i <= n» найдет это; иначе n никогда ни на что не будет делиться, и мы проверим это на «n > 1».

— 28.05.2019 05:16

На самом деле, использование «i * i <= n» делает алгоритм быстрее по сравнению с использованием «i <= n». Это превращает алгоритм O (n) в O (sqrt (n)) один.

— 28.05.2019 05:30

28.05.2019 03:29

def find_primes(n):
    factors = []
    i = 2
    if n == 0:
        return 0
    if n == 1:
        return 1
    while i <= n:
        if n % i == 0:
            factors.append(i)
            n /= i
        else:
            i += 1
    if len(factors) == 0:
        return "{} is a prime number.\n".format(initial_n)
    else:
        return "The prime factors of {} are: {}\n".format(initial_n, factors)


n = int(input("Enter a number to find all the Prime Factors:"))
initial_n = n
print('\n')
print(find_primes(n))

28.05.2019 03:46

Ответ принят как подходящий

Приведенная ниже функция для вычисления простых множителей намного проще, чем приведенная выше. Остальное — просто проверка правильности ввода пользователя.

###########################################################
#Main function to calculate prime factors
def find_prime_factors(n):
    factors = []
    p = 2
    while n > p ** 2:
        if n % p == 0:
            factors.append(p)
            n //= p
        else:
            p += 1
    factors.append(n)
    return factors
###########################################################

# Get User input
n = input('Enter a number to find all the Prime Factors: ') 

# Check if the entered value is a number
while not n.isnumeric():
    print('Entered number was not numeric.')
    n = input('Enter a NUMBER to find all the Prime Factors: ') 

# Check the entered value is greater than one (1)
# Prime Factor check happens on only positive numbers that are greater than one (1)

while int(n) < 2:
    print("Please enter a positive number that is greater than one (1).")
    n = input('Enter a NUMBER to find all the Prime Factors: ') 

#Python 3.7 string formating
print(f'The prime factor(s) of {n}: {find_prime_factors(int(n))} ')

28.05.2019 04:09