Задача к ЕГЭ по информатике на тему «делители числа» №3

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [1000; 123456789], числа, имеющие ровно 7 нечетных делителей. Программа должна вывести количество таких чисел.

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

x = p1q1 ⋅p2q2 ⋅...⋅pnqn

Здесь $pi,i ∈ [1;n]$ – некоторое простое число, а $qi,i ∈ [1;n]$ – натуральный показатель степени. В таком случае число обязательно имеет $(q1 + 1)⋅(q2 + 1)⋅...⋅(qn + 1)$ делителей (каждое простое число можно брать от 0 до $qi$ раз, где $i ∈ [1;n]$ ).

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

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

x = 2k ⋅p1q1 ⋅...⋅pnqn

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

(q1 + 1)⋅(q2 + 1)⋅...⋅(qn + 1)

Это количество должно быть равно $7$ – простому числу, а значит в этом произведении только один множитель, равный числу $7$ . Значит некоторое $(qi + 1) = 7$ , откуда $qi = 6$ . Поэтому число должно иметь следующий вид:

x = 2k ⋅p6

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

Таким образом, нужно будет перебрать простые числа $p$ (кроме $2$ ) и показатели $k$ степени числа $2$ так, чтобы получить все возможные числа вида $2k ⋅p6$ из отрезка $[1000;123456789]$ .

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) # вывод ответа

Ответ: 58