DjangoBB LoFi version

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

Начало » Центр помощи » Как ускорить выполнение скрипта?

1 2

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

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

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

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: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.

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

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

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

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

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

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

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

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