← Сtrl

pnk.andrian · Март 11, 2013 17:14:56

ks
Это как (сам процесс факторизации числа - при чем он здесь, не понятен)?

Факторизация числа - это представление числа в виде произведения простых чисел. Если вам надо получить список множителей не только для 600851475141, но и для 600851475141 + n, …, то этот способ предпочтительный. Если же вам надо один раз разложить на множители то будет достаточно и простого перебора:

n = 600851475141
m = []
for i in range(1, int(n**0.5), 2):
    if n % i == 0:
        m.extend([i, n/i])
print sorted(m)

doza_and · Март 11, 2013 20:06:52

:)

ks
Что вы посчитали?

Вы сказали что по вашим оценкам на вашей аппаратуре нужны миллисекунды на деление, вот я и посчитал сколько времени в годах надо для выполнения вашего цикла. Достаточно просто подождать 19 лет и цикл закончится.

Отредактировано doza_and (Март 11, 2013 20:07:30)

py.user.next · Март 12, 2013 01:52:10

pnk.andrian
Если же вам надо один раз разложить на множители то будет достаточно и простого перебора:
n = 600851475141
m = []
for i in range(1, int(n**0.5), 2):
    if n % i == 0:
        m.extend([i, n/i])
print sorted(m)

>>> n = 24
>>> m = []
>>> for i in range(1, int(n**0.5), 2):
...     if n % i == 0:
...         m.extend([i, n/i])
... 
>>> print sorted(m)
[1, 3, 8, 24]
>>>

>>> n = 25
>>> m = []
>>> for i in range(1, int(n**0.5), 2):
...     if n % i == 0:
...         m.extend([i, n/i])
... 
>>> print sorted(m)
[1, 25]
>>>

а вот ещё баг

>>> n = 121
>>> m = []
>>> for i in range(1, int(n**0.5) + 1, 2):
...     if n % i == 0:
...         m.extend([i, n/i])
... 
>>> print sorted(m)
[1, 11, 11, 121]
>>>

pnk.andrian
А при чем здесь простые числа?

притом, что ниоткуда не следует, что ему нужны простые делители числа (может, ему все делители нужны)
кстати, единица - не простое число

Отредактировано py.user.next (Март 12, 2013 02:03:19)

pnk.andrian · Март 12, 2013 17:33:29

py.user.next
а вот ещё баг

Багов нет. Универсального алгоритма я не обещал. Если нужен общий, относительно быстрый алгоритм, то факторизуем число (Факторизация целых чисел) и далее из простых множителей составляем все возможные.

py.user.next · Март 13, 2013 02:19:07

pnk.andrian
Багов нет. Универсального алгоритма я не обещал.

число повторяется два раза - это баг

Python-сообщество

Уведомления

#1 Март 11, 2013 17:14:56

Как ускорить выполнение скрипта?

#2 Март 11, 2013 20:06:52

Как ускорить выполнение скрипта?

#3 Март 12, 2013 01:52:10

Как ускорить выполнение скрипта?

#4 Март 12, 2013 17:33:29

Как ускорить выполнение скрипта?

#5 Март 13, 2013 02:19:07

Как ускорить выполнение скрипта?

Board footer