Работа с делителями

Пусть есть некоторая инициализированная переменная x, и мы хотим узнать все ее делители (обычно нас интересуют делители, не считая единицу и самого числа. Но если принципиально нужны и они, то просто в range изменим значения от 1 до x+1). Алгоритм будет выглядеть следующим образом

def getDels(x):
    dels=[]
    for i in range(2,x):
        if(x%i==0):
            dels.append(i)
    return dels

dels - список всех делителей числа x. Наиболее частые задачи, которые мы решаем - проверка числа на простоту, нахождение суммы минимального и максимального делителей, нахождение суммы всех делителей некоторого числа, нахождение минимального делителя с определенным условием.
Пусть мы вызвали функцию выше и записали результат в переменную dels.

x=int(input())
dels=getDels(x)

Проверка числа x на простоту.

if(dels==[]):
    print("Число x является простым")

Сумма минимального и максимального делителей числа x (т.к. в списке делители идут в порядке возрастания, то наименьший - это первый, а наибольший - последний).

sumMinMax=dels[0]+dels[-1]
print(sumMinMax)

Сумма всех делителей числа x

fullSum=sum(dels)
print(fullSum)

Пусть мы ищем максимальный делитель не кратный 3. Тогда  программа будет выглядеть следующим образом.

max3=0
for i in range(len(dels)):
    if(dels[i]%3!=0):
        max3=max(max3,dels[i])
print(max3)

Это наиболее интуитивный и алгоритмический способ работы с делителями, но наименее эффективный.

Для тех кто хочет знать больше:) (с 2025го года обязательно)

Заметим интересный факт. Если число делится на некоторый x, то оно делится и на результат деления на этот самый x. Так, например, 768 делится как на 2, так и на 768/2=384. Т.е. множители идут попарно (за исключением случая, когда x и результат деления на x совпадают и являются квадратным корнем исходного числа). Так, например, мы можем с уверенностью сказать, что если число не делится ни на одно из чисел не больших его квадратного корня, то оно простое. Напишем функцию проверки числа на простоту

def isPrime(x):
    for i in range(2,round(x**0.5)+1):
        if(x%i==0):
            return False
    return True

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

def getSumMinMax(x):
    res=0
    for i in range(2,round(x**0.5)+1):
        if(x%i==0):
            res=i+x//i
            break
    return res

Аналогично для поиска суммы всех делителей мы можем рассмотреть только те, которые не больше корня исходного числа, и сразу добавлять в сумму и парный делитель относительно найденного. Единственный момент, который нужно учесть - если нам попадется квадратный корень, то нужно его прибавить только один раз.

def getSumDels(x):
    res=0
    for i in range(2,round(x**0.5)+1):
        if(x%i==0):
            if(i!=x//i):
                res+=i+x//i
            else:
                res+=i
    return res

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

def getMaxDel3(x):
    res=0
    for i in range(2,round(x**0.5)+1):
        if(x%i==0):
            if(i%3==0):
                res=i
            if((x//i)%3==0):
                res=x//i
                break
    return res

В разборах задач вы часто можете увидеть оптимальную версию getDels. Идея всё та же, когда находим i, на которое делится x, то понимаем, что x еще делится на x//i. Но также, чтобы случайно не взять два одинаковых элемента, x//i берём, только в случае если оно не равно i.

def getDels(x):
    dels=[]
    for i in range(2,round(x**0.5)+1):
        if x%i==0:
            dels.append(i)
            if i!=x//i:
                dels.append(x//i)
    return dels