Python-сообщество

[code python][/code]

 a = 35000000
b =40000000
k = 0
for n in range(a, b + 1):
    ds = []
    for d in range(1, n,2):
        if n % d == 0:
            ds.append(d)
            if len(ds)>5:
                break
    if len(ds) == 5:
        print(n)

Отредактировано Lee (Март 25, 2021 17:30:54)

.

1. пжлст, форматируйте код, это в панели создания сообщений, выделите код и нажмите что то вроде
2. чтобы вставить изображение залейте его куда нибудь (например), нажмите и вставьте ссылку на его url
…
есчщо

Спасибо, что подсказали. Не знаете как решить такую задачу?

Lee
Если да, то кому не сложно напишите пожалуйста код…. Можно ли как нибудь ускорить этот процесс?

  for d in range(1, n,2):

[code python][/code]

Отредактировано PEHDOM (Март 25, 2021 18:18:06)

PEHDOM
1) Можно применить решето Эратосфена и из искомого диапазона вычеркнуть сразу все простые числа, чтобы не тратить время на проверку каждого из них на множественные делители.

2) Может стоит искать делители не последовательно, а рассматривать четность/нечетность делимого, делителя и частного.
Тут же не сказано в условии, что именно 5 наименьших делителей
Потенциальные делители тогда сверху сможем ограничить корнем квадратным из делимого, а значит еще сократить перебор.

Если число делится на 2 без остатка, то частное может быть четным и нечетным.
Например, 35000002 поделенное на 2 это 17500001. Получается, что при делении на 2 мы нашли один из искомых нечетных делителей. Но при этом каждый раз нам надо проверять четность частного, а это дополнительная операция.

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

Что мы имеем:
1) четное / четное - не можем судить о нечетности результата: может быть четным и нечетным
Следовательно, четные делимые имеет смысл проверять на деление на 2 и на степени числа 2.
Степенями двойки выявим делители типа таких 35000000 / 64 что дает 546875
2) четное / нечетное - если делится нацело, то результат всегда четный.
3) нечетное / четное - результат не будет целым числом. Следовательно, нечетные делимые нет смысла гонять по набору четных делителей.
4) нечетное / нечетное - если результат целое число, то нечетное. Следовательно, в этом случае наш счетчик нечетных делителей получает сразу +2 найденных нечетных делителя. Здесь даже контролировать четность частного дополнительной операцией не нужно.

В итоге имеем:
ШАГ 1: Выявляем и сохраняем массив простых чисел из искомого диапазона с помощью решета Эратосфена
ШАГ 2: проверяем делимое на четность. Тут е
Для нечетных делимых:
ШАГ 3: Проверяем есть ли это делимое в нашем массиве простых чисел или нет. Если нет, то:
ШАГ 4: Проверяем делимость на нечетные числа, которые меньше или равны корню квадратному из делимого. Помним, что каждый найденный делитель нам дает +2 к счетчику. Если не набрали искомое число делителей, то ответ “Нет”, если набрали - “Да”
Для четных делимых:
ШАГ 3: Проверяем делимость на нечетные числа, которые меньше или равны корню квадратному из делимого, при этом контролируем четность остатка, чтобы не пропустить комбинацию нечетное х нечетное = четное. Если нашли нужное количество делителей, выводим “да”, иначе шаг 4
ШАГ 4. Дополнительно проверяем четными делителями, а именно степенями числа 2. Если так и не нашлись, то выводим “Нет”, если нашлись, выводим “Да”.

Чтобы каждый раз не строить ряд нечетных делителей и степеней числа 2, их тоже можно вынести в отдельный шаг и сохранить как массив чисел. Рассчитать их до корня квадратного верхней границы диапазона включительно.

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

Пы.сы. Еще одна мысль вертится, что если в результате деления четного делимого на 2 мы получим простое число, то это тоже нам может сократить вычисления. Но пока не поняла как это можно эффективно использовать и на каком шаге. Вроде этот факт нам никак жизнь не облегчит, а может я ошибаюсь

Отредактировано Ocean (Апрель 16, 2021 23:48:26)

Ocean чесно говоря там все чутка сложнее и одновременно проще. Чисто эмпирически выяснилось “5 различных нечетных делителя” могут быть только в том случае если число имеет целочисленный корень. Математику под это к сожалению я не могу подвести. Так что просто проверяем если число не имеет целого корня, то отбрасываем его, если имеет то ищем все делители. Итого перебор занимает пару секунд.

[code python][/code]

Lee
Нужно вывести все числа которые имеют меньше 5 различных нечетных делителя(кол во четных может быть любым).

PEHDOM
Так что просто проверяем если число не имеет целого корня, то отбрасываем его, если имеет то ищем все делители.

Делители [4, 163, 53,681]
Число 35,000,012
Корень числа 5,916.08079729

  
>>> n = 35000012
>>> for i in range(1, n + 1):
...     if n % i == 0 and i % 2 != 0:
...         print(n, '->', i)
... 
35000012 -> 1
35000012 -> 163
35000012 -> 53681
35000012 -> 8750003
>>>

Отредактировано py.user.next (Апрель 19, 2021 01:09:46)

py.user.next
Поздравляю, ты выкинул подходящее число.

[code python][/code]

Отредактировано PEHDOM (Апрель 19, 2021 10:34:41)

PEHDOM
это другая задача, очень похожая но там нужно было найти ровно 5 нечетных делителей

Отредактировано py.user.next (Апрель 19, 2021 22:19:50)

py.user.next
Здесь, я так понял, нельзя фокусироваться на этом конкретном рассматриваемом диапазоне от 35000000 до 40000000 и использовать какие-то его свойства, присущие только ему, потому что в любой момент они могут взять и поменять диапазон на другой и сказать “а вот теперь для этого диапазона найдите всё то же самое”, из-за чего всё решение сразу посыпется, потому что чудесные свойства диапазона исчезнут.

py.user.next
Тут есть вещи, которые могут пригодиться

py.user.next
Да и единица тоже является нечётным делителем, поэтому мне непонятно, почему её решили исключать из этих пяти делителей? Ну и что, что единица. Нормальный делитель, ничем не хуже других.

py.user.next
Но я думаю, нужно число поделить на два и потом сверху вниз двигаться через одно число по нечётным.

Ocean
Можно применить решето Эратосфена и из искомого диапазона вычеркнуть сразу все простые числа, чтобы не тратить время на проверку каждого из них на множественные делители.

[code python][/code]

Отредактировано PEHDOM (Апрель 19, 2021 13:11:47)