0

Необходимо вычислить самый большой prime factor.

Написал две функции. Они работают на относительно небольших числах. Но на большом числе вычисление занимает реально много времени.

Что нибудь можно в них подправить или нужно полностью изменить концепцию?

def prime(n):
    total = []
    for x in range(2, n + 1):
        isPrime = True
        for y in range(2, x):
            if x % y == 0:
                isPrime = False
        if isPrime:
            total.append(x)
    return total


def all_prime(n):
    al = []
    s = prime(n)
    for x in s:
        if n % x == 0:
            al.append(x)
            n = n / x
    print (max(al))
2
  • похожий вопрос: Finding the greatest prime divisor (the fastest program possible)
    – jfs
    24 июн 2015 в 20:04
  • Если ответ вам помог, примите его с помощью зелёной галочки. Если нет - напишите комментарий под ответом, что именно непонятно или не получилось.
    – Mae
    29 мар 2017 в 8:33

1 ответ 1

6

Проблема жручего вычисления простых чисел - одна из самых проблемных в программировании (она же за счет этого обеспечивает защиту некоторых алгоритмов шифрования от брутфорса). Однако, в глаза бросаются сразу несколько вещей:

for y in range(2, x):
    if x % y == 0:
       isPrime = False

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

Во-вторых, вы проверяете все числа подряд. Включая четные, что делать не надо, потому что они, кроме двойки, априори не простые. Проверять на четность проще всего через битовую маску и проверку первого бита.

В-третьих, даже простое отсечение четных чисел не будет достаточно эффективным, все числа типа XYZ5 тоже можно смело отбрасывать, например. Достаточно проверять всего восемь чисел на каждые три десятка:

30n + 1
30n + 7
30n + 11
30n + 13
30n + 17
30n + 19
30n + 23
30n + 29

И, наконец, чтобы выяснить, является ли число N простым, не нужно делить его на все подряд от 2 до N. Достаточно дойти до квадратного корня из N. Аналогично и с наибольшим простым делителем - он не может быть больше N/2.

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.