Ctrl →

ks · Март 6, 2013 13:00:05

 for i in xrange(1, 600851475141):
   if 600851475141 % i == 0:
     print i

Да и вопрос интересует - почему, после некоторого момента, он наглухо виснет?
Тогда как отдельное взятие деления по модулю даже больших чисел занимает миллисекунды,
а перебор в цикле через итератор тоже вроде не ахти какая по сложности задача.

Отредактировано ks (Март 6, 2013 14:18:14)

pnk.andrian · Март 7, 2013 12:29:05

А вы серьезно считаете, что цикл из 600 милиардов итераций должен работать быстро?
Оптимизировать тут можно многое, например получить факторизацию числа и по ней составить список делителей. Но в вашем случае достаточно итерировать до квадратного корня по нечетным числам.

doza_and · Март 7, 2013 21:16:14

>>> import sympy.ntheory.primetest as pt 
>>> pt.isprime(600851475141)
False

Этот код несколько короче и несколько быстрее.
http://docs.sympy.org/dev/_modules/sympy/ntheory/primetest.html

Отредактировано doza_and (Март 7, 2013 21:16:46)

doza_and · Март 7, 2013 21:23:30

ks
после некоторого момента, он наглухо виснет?

>>> dt=1e-3;(600851475141*dt)/(3600*24*365)
19.05287528985921
Немного подождите.

Isem · Март 7, 2013 22:43:00

Уберите print

py.user.next · Март 8, 2013 04:11:02

pnk.andrian
Но в вашем случае достаточно итерировать до квадратного корня по нечетным числам.

а кто сказал, что это вывод всех простых чисел ?
разделить на два можно верхнюю границу

Isem
Уберите print

print там вообще очень редко происходит

pnk.andrian · Март 11, 2013 08:49:06

py.user.next
а кто сказал, что это вывод всех простых чисел ?
разделить на два можно верхнюю границу

А при чем здесь простые числа?
A*B = N
A < N**0.5 => B > N**0.5

Isem · Март 11, 2013 10:41:52

ks
Да и вопрос интересует - почему, после некоторого момента, он наглухо виснет?

Код виснет потому, что 600851475141 = 3*11981*16716787
и у этого числа нет делителей, больших 16716787.
Перебрать же 600851475141-16716787=600834758354 чисел на питоне нереально.

p.s. Имеется в виду простых делителей.
Ближайшие два делителя после 16716787 - это 50150361 и 200283825047.

Отредактировано Isem (Март 11, 2013 10:47:13)

ks · Март 11, 2013 16:07:23

pnk.andrian
получить факторизацию числа и по ней составить список делителей

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

pnk.andrian
А вы серьезно считаете, что цикл из 600 милиардов итераций должен работать быстро?

.))))) Ну подумаешь - не заметил порядок цифр.. я думал вполне реально и вот такое число перебрать: 100000000000000000000000000000000000 - ошибался.

ks · Март 11, 2013 16:07:59

doza_and
>>> dt=1e-3;(600851475141*dt)/(3600*24*365)
19.05287528985921
Немного подождите.

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

Отредактировано ks (Март 11, 2013 16:08:22)

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

Уведомления

#1 Март 6, 2013 13:00:05

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

#2 Март 7, 2013 12:29:05

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

#3 Март 7, 2013 21:16:14

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

#4 Март 7, 2013 21:23:30

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

#5 Март 7, 2013 22:43:00

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

#6 Март 8, 2013 04:11:02

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

#7 Март 11, 2013 08:49:06

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

#8 Март 11, 2013 10:41:52

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

#9 Март 11, 2013 16:07:23

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

#10 Март 11, 2013 16:07:59

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

Board footer