-6

Что можно оптимизировать в данной программе, находящей все простые делители натурального числа N?

import math
def pr(r,n):
    if n % r == 0:
        m = int(math.sqrt(r))
        g = 2
        while g <= m:
            if r % g == 0:
                return
            g += 1
        print(r, end=' ')
        return
    else:
        return
n = int(input())
pr(2, n)
for i in range(3, n + 1, 2):
    pr(i, n)
7
  • @sentique это наверно тоже стоит указать в вопросе. Вдобавок, хорошо бы привести шаги, которые вы предприняли, для того, чтобы оптимизировать эту программу. И это не программа, это - код программы.
    – Sublihim
    19 янв 2017 в 12:15
  • 3
    боюсь что ответ - всё. Тут сам алгоритм совсем не оптимален.
    – pavel
    19 янв 2017 в 12:40
  • 2
    Какова цель оптимизации? Скорость выполнения? Красота и (или) краткость кода? Что-то еще? 19 янв 2017 в 14:05
  • 3
    Если вас интересует скорость, а также современные алгоритмы нахождения простых чисел (от решета Эратосфена до алгоритма Аткина и Wheel Factorization) то очень рекомендую посмотреть вот этот шикарный ответ в английской версии SO 19 янв 2017 в 14:14
  • @MaxU если о скорости говорить, то стоит обратить внимание на комментарий, упоминающий pyprimesieve.
    – jfs
    20 янв 2017 в 7:40

1 ответ 1

0
def pr(r, n=2):
    while n <= r:
        if r % n:
            n += 1
        else:
            r //= n
            yield n

print(set(pr(110)))

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

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