0

Требуется найти наименьший делитель числа n>1. Ограничение по времени 1000 мс. Видимо проверяется на очень больших числах. Смог дойти до 55го теста и попадаю на превышение времени.

Как улучшить оптимизацию?

Код:

from math import sqrt


def mindivisor(n):
    if n % 2 == 0:
        return 2
    if n % 3 == 0:
        return 3
    if n % 5 == 0:
        return 5
    i = 7
    while n % i != 0:
        i += 2
        if i % 10 == 5:
            i += 2
    if i > sqrt(n):
        return n
    else:
        return i


n = int(input())
print(mindivisor(n))
0xdb
  • 51,614
slemik
  • 97

3 Answers3

2
while n % i != 0:

Тут вы проверяете все числа до n, хотя можно только до sqrt(n). Мне кажется, что основная проблема в этом. Попробуйте безо всяких проверок, просто в лоб:

def div(n):
    for i in range(2, int(sqrt(n)+1)):
        if n%i == 0:
            return i
    return n
Rennorb
  • 1,526
  • с этого я начал, потом сокращал. Минимум убрав чётные - перебор в 2 раза сокращается. Также перебор идёт до корня из n, просто проверка внутри – slemik Feb 12 '18 at 19:31
  • да, данный метод самый быстрый. Тут уже ускорить нечего :) – Денис Feb 13 '18 at 04:02
  • @Денис: есть и более быстрые методы факторизации больших чисел, к примеру Метод квадратичного решета – jfs Feb 13 '18 at 08:57
  • для больших чисел граница неправильная. Чтобы понять почему (одна из возможных причин) см.: Ляп в Питоне: x + 1.0 < x. Лучше ceil(sqrt(n))+1 использовать, чтобы с целыми дело иметь. Хотя здесь это скорее теоретическая проблема: подобный алгоритм со 100-битовыми числами до правой границы не дойдёт. – jfs Feb 13 '18 at 09:20
0

Итоговый код:

from math import sqrt, ceil


def mindivisor(n):
    if n % 2 == 0:
        return 2
    if n % 3 == 0:
        return 3
    if n % 5 == 0:
        return 5
    i = 7
    while n % i != 0:
        i += 2
        if i % 10 == 5:
            i += 2
        if i > ceil(sqrt(n)) + 1:
            return n
    return i


n = int(input())
print(mindivisor(n))

Проблема была в отступах перед if i > ceil(sqrt(n)) + 1:

slemik
  • 97
0

Вариант алгоритма перебора делителей c wheel factorization для множителей 2 и 3. Делители генерируются с шагом 2 и 4 по переменке. Транслировано с D кода:

from math import ceil, sqrt


def mindivisor(number):
    # manually test 1, 2, 3 and multiples of 2 and 3
    if number == 1:
        return 1
    elif number % 2 == 0:
        return 2
    elif number % 3 == 0:
        return 3

    # we can now avoid to consider multiples
    # of 2 and 3. This can be done really simply
    # by starting at 5 and incrementing by 2 and 4
    # alternatively, that is:
    #    5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, ...
    # we don't need to go higher than the square root of the number
    divisor = 5
    increment = 2
    sqrt_n = ceil(sqrt(number))
    while divisor <= sqrt_n:
        if number % divisor == 0:
            return divisor
        divisor += increment
        increment = 6 - increment  # 2 -> 4 -> 2

    return number  # number is prime


<script type="text/javascript" src="https://cdn.rawgit.com/brython-dev/brython/3.4.0/www/src/brython.js"></script><body onload="brython()"><script type="text/python">
from math import ceil, sqrt

def mindivisor(number):
    # manually test 1, 2, 3 and multiples of 2 and 3
    if number == 1:
        return 1
    elif number % 2 == 0:
        return 2
    elif number % 3 == 0:
        return 3


# we can now avoid to consider multiples
# of 2 and 3. This can be done really simply
# by starting at 5 and incrementing by 2 and 4
# alternatively, that is:
#    5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, ...
# we don't need to go higher than the square root of the number
divisor = 5
increment = 2
sqrt_n = ceil(sqrt(number))
while divisor &lt;= sqrt_n:
    if number % divisor == 0:
        return divisor
    divisor += increment
    increment = 6 - increment  # 2 -&gt; 4 -&gt; 2

return number  # number is prime




def show(n):
    print(f"{n} -> {mindivisor(n)}")


show(2209)

show(2201)


try your own input


from browser import document, alert 
@document["mybutton"].bind("click") 
def on_click(event):
    show(int(document["zone"].value))
</script>
<input id="zone" value="2021"><button id="mybutton">mindivisor</button></body>
jfs
  • 52,361