1

Назовём натуральное число подходящим, если у него больше 17 различных делителей (включая единицу и само число). Определите количество подходящих чисел, принадлежащих отрезку [10 001; 50 000], а также наименьшее из таких чисел. В ответе запишите два целых числа: сначала количество, затем наименьшее число.

sp = []
k=0
m=50001
for i in range(10001,50001):
    for j in range(1,i//2+1):
        if i%j==0:
            sp.append(j)
    if len(sp)>16:
        k+=1
        if i<m:
            m=i
    sp.clear()
print(k,m)

выводит ответ очень долго, что не дождаться

код добавляет все делители числа в список и потом если длин списка >16(хотя в условии сказано 17, но для того чтобы как то ускорить выше в делителях я сделал ограничение до половины числа, ибо дальше только делитель это само число, соответственно его в списке только не будет и значит в условии на один меньше)

как мог ускорил, но все равно не получается

1 ответ 1

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

Приходим к такому коду:

sp = set()
k=0
m=50001
for i in range(10001,50001):
    for j in range(1,int(i**0.5)+1):
        if i%j==0:
            sp.add(j)
            sp.add(i//j)
            if len(sp)>17:
                k+=1
                if i<m:
                    m=i
                break
    sp.clear()
print(k,m)

Я использую set, а не list только для того, чтобы не проверять является ли делитель корнем числа. В set число добавится только один раз, он об этом позаботится.

2
  • а зачем добавлять остаток от деления? если в задании сказано больше 17 делителей, а в список у нас уже идут тогда делители+ остатки от деления и соответственно длина списка становится больше, ответ выводит верный, но если убрать остатки от деления то неверно( не понимаю зачем добавлять в список остаток от деления
    – марат
    23 июл 2021 в 19:15
  • 1
    @марат Я немного не то написал, не остаток, конечно, а результат деления - ну, это по коду видно. Ведь это тоже делитель числа. А вы этот делитель просто потеряете, если будете идти до корня числа и не будете добавлять результат деления числа на делитель. Ну то есть грубо говоря возьмём число 100. 1 - делитель, но и 100/1=100 - делитель, 2 - делитель, но и 100/2=50, тоже делитель. Можно идя до корня числа сразу прибавлять по 2 делителя, а не по одному, что в 2 раза быстрее.
    – CrazyElf
    23 июл 2021 в 19:22

Ваш ответ

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

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