Как я могу уменьшить сложность пространства этого алгоритма факторизации? ⇐ Python

[Anonymous]

Я пытаюсь написать эффективную программу основной факторизации в качестве задачи по программированию, потому что факторизация действительно сложна. />

Код: Выделить всё

def factorize(n):
factors = (
[(2, exp)]
if (exp := (n & -n).bit_length() - 1)
else []
)

i = 3
while i**2 
Но на самом деле это намного медленнее для большинства случаев, это медленно факторизировать числа, которые не близки к идеальным квадратам, а факторизация основных чисел занимает слишком много времени. Я, конечно, могу использовать список простых чисел для определения раннего возврата самой глубокой рекурсии, но, как упоминалось выше, моя оперативная память конечна ... < /p>
Этот вопрос не о двух вышеупомянутых алгоритмах , Я включил их, чтобы показать свое исследование. Поэтому я придумал свой собственный алгоритм, я не знаю, думал ли кто -нибудь об этом раньше, но я написал это менее чем за 15 минут. Это очень быстро, но требует гораздо больше оперативной памяти, чем два выше, и работает только для конечного количества входов. Каждое число отмечено как Prime, отметьте все его кратные как кратные Prime, поэтому мы получим отображение всех композитов в диапазоне с одним из их факторов, тогда мы можем просто многократно разделить число (в пределах диапазона) на его Связанный фактор, пока число не будет найдено в картировании (следовательно, оно было уменьшено до первого). < /p>
время выполнения почти постоянно, но вычисление таблицы занимает много Времени и содержания памяти. < /p>
import numpy as np
from itertools import cycle
TRIPLE1 = ((4, 2, 2), (9, 6, 3), (25, 10, 5))
WHEEL = (4, 2, 4, 2, 4, 6, 2, 6)

def min_prime_factors(n):
primes = np.ones(n + 1, dtype=bool)
primes[:2] = False
composites = {}
for square, double, prime in TRIPLE1:
primes[square::double] = False
for i in range(square, n + 1, double):
composites[i] = prime

wheel = cycle(WHEEL)
k = 7
while (square := k**2)  2**25:
raise ValueError("Number too large")

factors = []
while n > 1 and (index := MIN_FACTORS.get(n)):
prime = PRIME_LIST[index]
factors.append(prime)
n //= prime

if n > 1:
factors.append(n)

return factors
< /code>
Это требуется намного меньше, чем микросекунда для факторизации большинства чисел, но таблица занимает около 2,5 ГБ ОЗУ, а предел алгоритма довольно мал, я попытался использовать это для генерации Таблица для чисел до 2^30, но для запуска потребовалось вечно, и она использовала более 10 Гиб ОЗУ, мне пришлось прервать ее. < /p>
Как я могу заставить ее потреблять меньше памяти? Я предполагаю, что это невозможно. Теперь, это тривиально, чтобы определить силы двух, поэтому мне нужно сохранить только нечетные числа и номера карт для индексов по этому: (n - 3) // 2 

, это сокращает использование памяти таблицы половина, но это не уменьшает потребление памяти во время просеивания, и этого недостаточно. п>

Подробнее здесь: https://stackoverflow.com/questions/793 ... -algorithm