Как найти максимально возможный нечетный множитель числа

Question

Для программы, которую я пишу, я придумал способ сэкономить огромное количество времени.Чтобы сделать это, мне нужно знать, как найти максимально возможный простой множитель числа определенного размера.Например:

N = 9868690954602957859
N_MAX_FACTOR_BITSIZE = 64

Затем я запускаю N по этому алгоритму:

p = floor(sqrt(n))
if p mod 2 == 0:
    p += 1
while p < N:  # Referenced above
    if p mod n == 0:
        return p
    p += 2

Этот алгоритм работает по принципу, что над floor(sqrt(N)) есть только два простых числа, которыеразделит N равномерно.Поскольку оба числа будут простыми, алгоритм проверяет только нечетные числа.

Чтобы сократить время, которое занимает этот алгоритм, я хотел бы поменять N в while p < N с наибольшим нечетным 64-битным числом, котороеможет умножиться на N.

Например, алгоритм, который принимает N и N_MAX_FACTOR_BITSIZE в качестве аргументов и возвращает наибольший нечетный множитель N, который имеет длину N_MAX_FACTOR_BITSIZE.

Возвращаемое число должно быть N_MAX_FACTOR_BITSIZE бит длиной.

Любая помощь будет оценена.

Answer 1

Эта функция возвращает наибольшее количество n битов, а возвращаемое число всегда нечетно. (По крайней мере, до 1 миллиона бит)

def largest_bitsize(n):
    return ~(-1 << n)

Answer 2

def prime_factors(n):
    """Returns all the prime factors of a positive integer"""
    factors = []
    d = 2
    while n > 1:
        while n % d == 0:
            factors.append(d)
            n /= d
        d = d + 1

    return factors

n = 9868690954602957859

primes =prime_factors(n)[-1]

print(primes)