0 / 0 / 0
Регистрация: 06.05.2018
Сообщений: 2
1

Все простые делители числа

23.04.2019, 09:26. Показов 6038. Ответов 1

Author24 — интернет-сервис помощи студентам
Здравствуйте, написал код для нахождения всех простых делителей числа, но он долго работает (я пробовал n=600851475143). Подскажите, пожалуйста, как можно оптимизировать. Может есть какие-то принципиально отличающиеся идеи, как можно решить данную задачу?


сам код (star,running и end чисто для того, чтобы видеть, что что-то происходит):

def alldiv(n):
from math import sqrt
print('alldiv start')
lst=[]
n1=int(sqrt(n))
for i in range(2,n1+1):
if n%i==0:
lst.append(i)
lst.append(n//i)
print('alldiv is running')
print('alldiv end')
return(lst)


def isprime(i):
print('isprime start')
a=2
while a*a<=i:
if i%a==0:
return False
a+=1
print('isprime is running')
print('isprime end')
return True


n=int(input())
lst=alldiv(n)
primediv=[]
for i in range(len(lst)):
if isprime(lst[i])==True:
primediv.append(lst[i])
print(*primediv)
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.04.2019, 09:26
Ответы с готовыми решениями:

Зная простые делители числа и их количество, найти все делители числа
Добрый вечер. Есть задача: зная простые делители числа и их количество, найти все делители числа....

Получить все простые делители числа
Дано натуральное число n. Получить все простые делители этого числа Перевести на Python CLS...

Получить все делители числа q, взаимно простые с p
Даны целые числа p и q. Получить все делители числа q, взаимно простые с p.

Получить все делители числа q, взаимно простые с p. Сделать блок схему
Получить все делители числа q, взаимно простые с p Сделать блок схему. Заранее спасибо.

1
121 / 100 / 79
Регистрация: 30.11.2017
Сообщений: 230
23.04.2019, 18:17 2
Это задача на динамическое программирование. Почитайте про это. Идея в том, что результаты промежуточных вычислений нужно кэшировать, а не вычислять заново на каждой итерации цикла.
0
23.04.2019, 18:17
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
23.04.2019, 18:17
Помогаю со студенческими работами здесь

Дано натуральное число n> 1. Выведите все простые делители этого числа в порядке возрастания с учетом кратности
Нужно как-то упростить код, но так, что бы присутствовала рекурсия. Если кто сможет, буду очень...

Найти все трехзначные простые числа. (Определить функцию, позволяющую распознавать простые числа.)
Найти все трехзначные простые числа. (Определить функцию, позволяющую распознавать простые...

Даны натуральные числа p и q. Получить все делители числа q, взаимнопростые с p
как исправить, чтобы выводились только те делители, которые взаимнопросты с p? x=int(input('x='))...

Найти все делители натурального числа N.
Найти все делители натурального числа N.

Найти все делители натурального числа
# TASK # Найти все делители данного натурального числа N. N = int (input ('Введите число: '))...

Вывести все делители числа в порядке возрастания
Простыми называются такие натуральные числа, у которых ровно два делителя: 1 и само это число (они...

Вывести все делители данного числа в порядке возрастания
Вывести все делители данного числа в порядке возрастания


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru