25.01 Делители числа

По основной теореме арифметики (ОТА) каждое натуральное число, большее 1, можно разложить на простые множители. То есть некоторое натуральное число можно разложить в следующий вид:

Здесь – некоторое простое число, а – натуральный показатель степени. В таком случае число обязательно имеет делителей (каждое простое число можно брать от 0 до раз, где ).

В данной задаче необходимо, чтобы у числа было ровно нечётных делителей. Значит число должно содержать в разложении простые числа, помимо , чтобы такие делители были.

Пусть число имеет следующий вид (отдельно выпишем простое число в разложении):

Выпишем количество нечётных делителей числа:

Это количество должно быть равно – простому числу, а значит в этом произведении только один множитель, равный числу . Значит некоторое , откуда . Поэтому число должно иметь следующий вид:

Здесь показатель степени k может быть любым неотрицательным числом, так как степень числа не влияет на количество нечётных делителей.

Таким образом, нужно будет перебрать простые числа (кроме ) и показатели степени числа так, чтобы получить все возможные числа вида из отрезка .

def simple(x): # функция для проверки, что число - простое
    for d in range(2,int(x**0.5)+1):
        if x % d == 0:
            return False
    return True

count = 0 # cчётчик чисел
simple_numbers = [x for x in range(3,int(123456789 ** (1/6))+1) if simple(x)] # список, в котором хранятся простые числа от 3 до корня 6-ой степени правой границы
for number in simple_numbers: # проход по простым числам
    for i in range(20): # проход по различным степеням для двойки
        if 1000 <= number**6 * 2**i <= 123456789: # проверка по условию
            count += 1
print(count) # вывод ответа