25.04 Основная теорема арифметики - Каталог заданий по ЕГЭ

Ошибка.
Попробуйте повторить позже

Задача 1#13989Максимум баллов за задание: 1

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [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

Ошибка.
Попробуйте повторить позже

Задача 2#22055Максимум баллов за задание: 1

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

Показать ответ и решение

По основной теореме арифметики (ОТА) каждое натуральное число, большее 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]$ ).

В данной задаче необходимо, чтобы у числа было ровно 11 натуральных делителей.

Тогда произведение всех $qi$ должно быть равно 11. Так как число 11 – простое, то только 1 множитель должен быть равен 11. Отсюда некоторое $q = 10 i$ .

Тогда число имеет вид $10 p$ где $p$ – любое простое число.

Таким образом, нужно будет перебрать простые числа так, чтобы получить все возможные числа вида $p10$ из отрезка $[123456789;987654321]$ .

def is_prime(n):  # Функция проверки на простое число
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:  # Если нашли нетривиальный делитель
            return False  # То число не простое, возвращаем False
    return n > 1  # Если число равно 1, то оно непростое, и будет возвращено False, а иначе True


ans = []  # Список чисел для ответа

# Нужно перебрать все числа вида x = p**10, где p - простое число

# Находим максимально возможное p для отрезка
p_max = int(987654321 ** (1 / 10))

# Перебираем простые числа от 2 до максимально возможного
for p in range(2, p_max + 1):
    if is_prime(p):  # Если число p - простое
        # То проверяем, что итоговое число будет принадлежать отрезку
        if 123456789 <= p ** 10 <= 987654321:
            ans.append(p ** 10)

print(*sorted(ans)) # Выводим ответ в порядке возрастания

Ответ: 282475249

Ошибка.
Попробуйте повторить позже

Задача 3#22056Максимум баллов за задание: 1

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку $[1234567;7654321]$ , числа, у которых ровно $7$ делителей, сумма цифр которых некратна $3$ . Количество делителей, чья сумма цифр кратна $3$ , может быть любым. Программа должна вывести количество таких чисел.

Показать ответ и решение

По основной теореме арифметики (ОТА) каждое натуральное число, большее 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 делителей, сумма цифр которых некратна 3. Это означает, что сами делители некратны 3, а значит число должно содержать в разложении простые числа, помимо 3.

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

k q1 qn x = 3 ⋅p1 ⋅...⋅pn

Выпишем количество делителей числа, которые некратны 3:

(q + 1)⋅(q + 1)⋅...⋅(q + 1) 1 2 n

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

k 6 x = 3 ⋅p

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

Таким образом, нужно будет перебрать простые числа p (исключая 3) так, чтобы получить все возможные числа вида $k 6 3 ⋅p$ из отрезка $[1732864;7146924]$ .

import math


def is_prime(n): # Функция проверки на простое число
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:  # Если нашли нетривиальный делитель
            return False  # То число не простое, возвращаем False
    return n > 1  # Если число равно 1, то оно непростое, и будет возвращено False, а иначе True


ans = 0  # Счётчик для ответа

# Нужно перебрать все числа вида x = 3**k * p**6, где p - простое число (кроме 3)

# Находим максимальное возможное k для отрезка через логарифм по основанию числа 3
k_max = int(math.log(7654321, 3))

# Находим максимально возможное p для отрезка
p_max = int(7654321 ** (1 / 6))

# Перебираем простые числа от 2 до максимально возможного
for p in range(2, p_max + 1):
    if p != 3 and is_prime(p):  # Если число p - простое и не равно 3
        for k in range(k_max + 1):  # Перебираем до k_max включительно
            if 1234567 <= 3 ** k * p ** 6 <= 7654321:  # Проверяем, что итоговое число будет принадлежать отрезку
                ans += 1
print(ans)

Ответ: 8

Ошибка.
Попробуйте повторить позже

Задача 4#22057Максимум баллов за задание: 1

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку $[12345678;87654321]$ , числа, у которых есть ровно $5$ делителей, которые оканчиваются на $0$ или $5$ . Общее количество делителей числа может быть любым. Программа должна вывести количество таких чисел.

Показать ответ и решение

По основной теореме арифметики (ОТА) каждое натуральное число, большее 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]$ ).

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

Пусть число имеет следующий вид:

k q1 qn x = 5 ⋅p1 ⋅...⋅pn

В таком случае количество делителей, кратных 5, будет равно $k ⋅(q1 + 1)⋅(q2 + 1)⋅...⋅(qn + 1),$ обозначим произведение всех $qi$ за $m$ . Так как количество по условию должно быть равно 5, то либо $k = 5$ и $m = 1$ , либо $k = 1$ и $m = 5$ . Для $m = 5$ аналогично будет только 1 множитель, а значит только 1 простое число в степени с показателем 4. В общем случае это можно представить, как $1 4 5 ⋅p ,$ где $p$ – любое простое число (в том числе 5, что обобщает эти два случая).

Таким образом, нужно будет перебрать простые числа так, чтобы получить все возможные числа вида $p4 ⋅5$ из отрезка $[12345678;87654321]$ .

def is_prime(n):  # Функция проверки, является ли число простым
    if n == 1:  # Единицу нужно проверить отдельно
        return False  # 1 - не простое число, возвращаем False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:  # Если нашли нетривиальный делитель
            return False  # То число не простое, возвращаем False
    return True


ans = 0  # Счётчик для ответа

# Нужно перебрать все числа вида x = 5 * p**4, где p - простое число

l = 12345678  # Левая граница отрезка
# Делим на 5, а затем извлекаем корень 4 степени,
# чтобы получить первое возможное p
l = int((l / 5) ** (1 / 4))

# Аналогично с правой границей отрезка
r = 87654321
r = int((r / 5) ** (1 / 4))

# Перебираем числа от l до r включительно
for p in range(l, r + 1):
    if is_prime(p):  # Если число p - простое
        # Проверяем, что итоговое число будет принадлежать отрезку
        if 12345678 <= 5 * p ** 4 <= 87654321:
            ans += 1
print(ans)

Ответ: 6

Ошибка.
Попробуйте повторить позже

Задача 5#25110Максимум баллов за задание: 1

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку $[28916485;49716586]$ , числа, у которых есть ровно $5$ делителей, которые оканчиваются на $0$ или $5$ . Общее количество делителей числа может быть любым. В ответ запишите все найденные числа через пробел в порядке возрастания.

Показать ответ и решение

По основной теореме арифметики (ОТА) каждое натуральное число, большее 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]$ ).

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

Пусть число имеет следующий вид:

k q1 qn x = 5 ⋅p1 ⋅...⋅pn

В таком случае количество делителей, кратных 5, будет равно $k ⋅(q1 + 1)⋅(q2 + 1)⋅...⋅(qn + 1),$ обозначим произведение всех $qi$ за $m$ . Так как количество по условию должно быть равно 5, то либо $k = 5$ и $m = 1$ , либо $k = 1$ и $m = 5$ . Для $m = 5$ аналогично будет только 1 множитель, а значит только 1 простое число в степени с показателем 4. В общем случае это можно представить, как $1 4 5 ⋅p ,$ где $p$ – любое простое число (в том числе 5, что обобщает эти два случая).

Таким образом, нужно будет перебрать простые числа так, чтобы получить все возможные числа вида $p4 ⋅5$ из отрезка $[28916485;49716586]$ .

def is_prime(n):  # Функция проверки, является ли число простым
    if n == 1:  # Единицу нужно проверить отдельно
        return False  # 1 - не простое число, возвращаем False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:  # Если нашли нетривиальный делитель
            return False  # То число не простое, возвращаем False
    return True

# Нужно перебрать все числа вида x = 5 * p**4, где p - простое число

l = 28916485  # Левая граница отрезка
# Делим на 5, а затем извлекаем корень 4 степени,
# чтобы получить первое возможное p
l = int((l / 5) ** (1 / 4))

# Аналогично с правой границей отрезка
r = 49716586
r = int((r / 5) ** (1 / 4))

# Перебираем числа от l до r включительно
ans = []  # Список чисел для ответа
for p in range(l, r + 1):
    if is_prime(p):  # Если число p - простое
        # Проверяем, что итоговое число будет принадлежать отрезку
        if 28916485 <= 5 * p ** 4 <= 49716586:
            ans.append(5 * p ** 4)

print(*ans)  # Выводим элементы списка через пробел

Ответ: 39452405

Ошибка.
Попробуйте повторить позже

Задача 6#25596Максимум баллов за задание: 1

Найдите все натуральные числа, принадлежащие отрезку [101 000 000; 102 000 000], у которых ровно три различных чётных делителя. Общее количество делителей может быть любым. В ответе перечислите найденные числа через пробел в порядке возрастания.

Показать ответ и решение

По основной теореме арифметики (ОТА) каждое натуральное число, большее 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]$ ).

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

Пусть число имеет следующий вид:

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

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

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

Выпишем количество делителей числа, не содержащих степень числа 2, то есть не являющихся чётными:

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

Из общего количества делителей вычтем количество делителей, не являющихся чётными, и получим количество чётных делителей:

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

Обозначим произведение всех $qi$ за $m$ . Так как количество по условию должно быть равно 3, то $k⋅m = 3$ . Так как число 3 – простое, то либо $k = 3$ и $m = 1$ , либо $k = 1$ и $m = 3$ .

В первом случае это число $23$ , так как $m = 1$ означает, что других простых чисел в разложении числа нет.

Во втором случае произведение всех $qi$ равно 3, а значит только 1 множитель должен быть равен 3. Поэтому число будет иметь вид $21 ⋅p2$ .

В общем случае это можно представить, как $2 2⋅p ,$ где $p$ – любое простое число (включая число 2, что обобщает эти два случая).

Таким образом, нужно будет перебрать простые числа так, чтобы получить все возможные числа вида $2 ⋅p2$ из отрезка $[101000000;102000000]$ .

def is_prime(n):  # Функция проверки, является ли число простым
    if n == 1:  # Единицу нужно проверить отдельно
        return False  # 1 - не простое число, возвращаем False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:  # Если нашли нетривиальный делитель
            return False  # То число не простое, возвращаем False
    return True

# Нужно перебрать все числа вида x = 2 * p**2, где p - простое число

l = 101_000_000  # Левая граница отрезка
# Делим на 2, а затем извлекаем корень 2 степени,
# чтобы получить первое возможное p
l = int((l / 2) ** (1 / 2))

# Аналогично с правой границей отрезка
r = 102_000_000
r = int((r / 2) ** (1 / 2))

# Перебираем числа от l до r включительно
ans = []  # Список чисел для ответа
for p in range(l, r + 1):
    if is_prime(p):  # Если число p - простое
        # Проверяем, что итоговое число будет принадлежать отрезку
        if 101_000_000 <= 2 * p ** 2 <= 102_000_000:
            ans.append(2 * p ** 2)

print(*ans)  # Выводим элементы списка через пробел

Ответ: 101075762 101417282 101588258 101645282

Ошибка.
Попробуйте повторить позже

Задача 7#26104Максимум баллов за задание: 1

Найдите все натуральные числа, принадлежащие отрезку [95 000 000; 130 000 000], у которых ровно пять различных чётных делителей. Общее количество делителей может быть любым. В ответе перечислите найденные числа в порядке убывания.

Показать ответ и решение

По основной теореме арифметики (ОТА) каждое натуральное число, большее 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]$ ).

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

Пусть число имеет следующий вид:

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

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

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

Выпишем количество делителей числа, не содержащих степень числа 2, то есть не являющихся чётными:

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

Из общего количества делителей вычтем количество делителей, не являющихся чётными, и получим количество чётных делителей:

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

Обозначим произведение всех $qi$ за $m$ . Так как количество по условию должно быть равно 5, то $k⋅m = 5$ . Так как число 5 – простое, то либо $k = 5$ и $m = 1$ , либо $k = 1$ и $m = 5$ .

В первом случае это число $25$ , так как $m = 1$ означает, что других простых чисел в разложении числа нет.

Во втором случае произведение всех $qi$ равно 5, а значит только 1 множитель должен быть равен 5 (так как 5 – простое число). Поэтому число будет иметь вид $21 ⋅p4$ .

В общем случае это можно представить, как $4 2⋅p ,$ где $p$ – любое простое число (включая число 2, что обобщает эти два случая).

Таким образом, нужно будет перебрать простые числа так, чтобы получить все возможные числа вида $2 ⋅p4$ из отрезка $[95000000;130000000]$ .

def is_prime(n):  # Функция проверки, является ли число простым
    if n == 1:  # Единицу нужно проверить отдельно
        return False  # 1 - не простое число, возвращаем False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:  # Если нашли нетривиальный делитель
            return False  # То число не простое, возвращаем False
    return True


# Нужно перебрать все числа вида x = 2 * p**4, где p - простое число

l = 95_000_000  # Левая граница отрезка
# Делим на 2, а затем извлекаем корень 4 степени,
# чтобы получить первое возможное p
l = int((l / 2) ** (1 / 4))

# Аналогично с правой границей отрезка
r = 130_000_000
r = int((r / 2) ** (1 / 4))

ans = []  # Список чисел для ответа
# Переберём числа в порядке убывания для заполнения списка в порядке убывания
for p in range(r, l - 1, -1):
    if is_prime(p):  # Если число p - простое
        # Проверяем, что итоговое число будет принадлежать отрезку
        if 95_000_000 <= 2 * p ** 4 <= 130_000_000:
            ans.append(2 * p ** 4)

print(*ans)  # Выводим элементы списка через пробел

Ответ: 125484482

Ошибка.
Попробуйте повторить позже

Задача 8#26987Максимум баллов за задание: 1

Найдите все натуральные числа, принадлежащие отрезку [20 000 000;25 000 000], у которых ровно пять различных нечётных делителей. Общее количество делителей может быть любым. В ответе перечислите найденные числа через пробел в порядке возрастания.

Показать ответ и решение

По основной теореме арифметики (ОТА) каждое натуральное число, большее 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]$ ).

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

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

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

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

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

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

k 4 x = 2 ⋅p

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

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

def is_prime(n):  # Функция проверки, является ли число простым
    if n == 1:  # Единицу нужно проверить отдельно
        return False  # 1 - не простое число, возвращаем False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:  # Если нашли нетривиальный делитель
            return False  # То число не простое, возвращаем False
    return True


# Нужно перебрать все числа вида x = 2**k * p**4, где p - простое число

r = 25_000_000  # Левая граница отрезка
r = int(r ** (1 / 4))  # Извлечём корень 4 степени, чтобы получить максимальное возможное p

# Перебираем числа от l до r включительно
ans = []  # Список чисел для ответа
for p in range(3, r + 1):  # Перебираем возможные простые числа
    if is_prime(p):  # Если число p - простое
        # Пока число не выйдет за верхнюю границу отрезка,
        # будем проверять его и увеличивать степень числа 2
        num = p ** 4
        while num <= 25_000_000:
            if 20_000_000 <= num <= 25_000_000:
                ans.append(num)
            num *= 2  # Увеличиваем степень числа 2

print(*sorted(ans))  # Выводим элементы сортированного списка через пробел

Ответ: 20151121 20480000 21233664 21381376 22606088 22632992 24234722

Ошибка.
Попробуйте повторить позже

Задача 9#27468Максимум баллов за задание: 1

Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку $[1732864;7146924]$ числа, у которых ровно $7$ делителей, сумма цифр которых некратна $3$ . Общее количество делителей может быть любым. Программа должна вывести количество таких чисел.

Показать ответ и решение

По основной теореме арифметики (ОТА) каждое натуральное число, большее 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 делителей, сумма цифр которых некратна 3. Это означает, что сами делители некратны 3, а значит число должно содержать в разложении простые числа, помимо 3.

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

k q1 qn x = 3 ⋅p1 ⋅...⋅pn

Выпишем количество делителей числа, которые некратны 3:

(q + 1)⋅(q + 1)⋅...⋅(q + 1) 1 2 n

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

k 6 x = 3 ⋅p

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

Таким образом, нужно будет перебрать простые числа p (исключая 3) так, чтобы получить все возможные числа вида $k 6 3 ⋅p$ из отрезка $[1732864;7146924]$ .

import math


def is_prime(n):
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:  # Если нашли нетривиальный делитель
            return False  # То число не простое, возвращаем False
    return n > 1  # Если число равно 1, то оно непростое, и будет возвращено False, а иначе True


ans = 0  # Счётчик для ответа

# Нужно перебрать все числа вида x = 3**k * p**6, где p - простое число (кроме 3)

# Находим максимальное возможное k для отрезка через логарифм по основанию числа 3
k_max = int(math.log(7146924, 3))

# Находим максимально возможное p для отрезка
p_max = int(7146924 ** (1 / 6))

# Перебираем простые числа от 2 до максимально возможного
for p in range(2, p_max + 1):
    if p != 3 and is_prime(p):  # Если число p - простое и не равно 3
        for k in range(k_max + 1):  # Перебираем до k_max включительно
            if 1732864 <= 3 ** k * p ** 6 <= 7146924:  # Проверяем, что итоговое число будет принадлежать отрезку
                ans += 1
print(ans)

Ответ: 6

Ошибка.
Попробуйте повторить позже

Задача 10#30244Максимум баллов за задание: 1

Найдите все натуральные числа, принадлежащие отрезку [ $33$ $333$ $333$ ; $99$ $999$ $999$ ], у которых ровно $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.

Пусть число имеет следующий вид:

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

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

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

Выпишем количество делителей числа, не содержащих степень числа 2, то есть не являющихся чётными:

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

Из общего количества делителей вычтем количество делителей, не являющихся чётными, и получим количество чётных делителей:

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

Обозначим произведение всех $qi$ за $m$ . Так как количество по условию должно быть равно 7, то $k⋅m = 7$ . Так как число 7 – простое, то либо $k = 7$ и $m = 1$ , либо $k = 1$ и $m = 7$ .

В первом случае это число $27$ , так как $m = 1$ означает, что других простых чисел в разложении числа нет.

Во втором случае произведение всех $qi$ равно 7, а значит только 1 множитель должен быть равен 7 (так как 7 – простое число). Отсюда некоторое $qi = 6$ . Поэтому число будет иметь вид $21 ⋅p6$ .

В общем случае это можно представить, как $6 2⋅p ,$ где $p$ – любое простое число (включая число 2, что обобщает эти два случая).

Таким образом, нужно будет перебрать простые числа так, чтобы получить все возможные числа вида $2 ⋅p6$ из отрезка $[33333333;99999999]$ .

def is_prime(n):  # Функция проверки на простое число
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:  # Если нашли нетривиальный делитель
            return False  # То число не простое, возвращаем False
    return n > 1  # Если число равно 1, то оно непростое, и будет возвращено False, а иначе True


ans = 0  # Счётчик для ответа

# Нужно перебрать все числа вида x = 2 * p**6, где p - простое число

# Находим максимально возможное p для отрезка
p_max = int(99_999_999 ** (1 / 6))

# Перебираем простые числа от 2 до максимально возможного
for p in range(2, p_max + 1):
    if is_prime(p):  # Если число p - простое
        # То проверяем, что итоговое число будет принадлежать отрезку
        if 33_333_333 <= 2 * p ** 6 <= 99_999_999:
            ans += 1
print(ans)

Ответ: 2

Ошибка.
Попробуйте повторить позже

Задача 11#30249Максимум баллов за задание: 1

Назовём числа $a$ и $b$ числами-близнецами, если $|a − b| = 2$ .

Найдите наименьшее натуральное число, имеющее ровно 512 делителей, простые делители которого образуют не менее трёх пар чисел-близнецов. В ответе укажите число, а также все его простые делители.

Показать ответ и решение

По основной теореме арифметики (ОТА) каждое натуральное число, большее 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]$ ).

Теперь перейдём к решению задачи. Необходимо найти наименьшее натуральное число, имеющее ровно $512$ , то есть $29$ делителей. При этом простые делители должны образовать не менее $3$ пар чисел-близнецов.

Получается, раз всего делителей $29$ , то произведение всех $q i$ состоит максимум из $9$ множителей, каждый из которых равен $2$ . Либо множителей меньше, и тогда какой-то множитель будет увеличен в $2$ раза за счёт убранного. Тогда все степени простых чисел, которые участвуют в разложении, будут иметь нечётный показатель среди чисел $[1,3,7,15,31,63,127,255,511]$ (степени числа $2$ от $1$ до $9$ с вычетом $1$ ).

Если число должно быть минимальным, то оно раскладываться в минимальное произведение простых чисел. Тогда выпишем первые 9 простых чисел по возрастанию:

2,3,5,7,11,13,17,19,23

Больше $9$ простых чисел брать не нужно, так как максимум в числе должно быть $9$ множителей $(q + 1) i$ , что означает максимальное количество простых множителей $9$ .

Так как каждому из $9$ простых чисел можно дать любую степень от $0$ до $511$ (всего $10$ вариантов), а также всего простых чисел ровно $9$ , то при обычном комбинаторном переборе (например при использовании product) будет получено $9 10$ вариантов разложения, что очень много и явно избыточно для получения минимального требуемого числа. Поэтому решим задачу с использованием рекурсивной функции, которая будет прекращать своё выполнение при нарушении условия по количеству делителей.

primes = [2, 3, 5, 7, 11, 13, 17, 19, 23]  # Необходимые простые числа
degrees = [1, 3, 7, 15, 31, 63, 127, 255, 511]  # Возможные показатели степеней (кроме 0)
ans = []  # Список, в который будут добавляться подходящие числа и их простые делители


# Рекурсивная функция для получения возможных чисел
# Аргументы:
#   index - индекс простого числа из списка primes
#   num - текущее полученное число
#   num_primes - простые делители, входящие в разложение числа num
#   divs_count - текущее количество делителей числа num
#   twins_count - количество чисел-близнецов среди простых делителей
def F(index, num, num_primes, divs_count, twins_count):
    # Превысили требуемое количество делителей
    if divs_count > 512:
        return  # Выход из рекурсии

    # Все простые числа были рассмотрены (взята их степень от 0 до 511)
    if index == len(primes):
        if divs_count == 512 and twins_count >= 3:  # Проверка выполнения условий
            ans.append((num, *num_primes))  # Добавляем число и его делители в список
        return  # Выход из рекурсии

    # Запуск рекурсии при отсутствии текущего простого числа primes[index] (степень 0)
    # Здесь изменяется только индекс (index+1) для взятия следующего простого числа
    F(index + 1, num, num_primes, divs_count, twins_count)

    p = primes[index]  # Текущее взятое простое число
    # Проверка наличия новой пары чисел-близнецов
    if len(num_primes) > 0 and p - num_primes[-1] == 2:
        twins_count += 1
    # Перебор показателей степеней от 1 до 511
    for q in degrees:
        new_num = num * p ** q  # Новое число
        new_num_primes = num_primes + [p]  # Список простых делителей нового числа
        new_divs_count = divs_count * (q + 1)  # Количество делителей нового числа
        # Запуск рекурсии для нового числа и его параметров
        F(index + 1, new_num, new_num_primes, new_divs_count, twins_count)
                                                                                                     
                                                                                                     


# Запускаем рекурсию
# Исходные параметры:
#   index = 0, так как индексация в списке начинается с 0
#   num = 1, так как для получения произведения нужно брать 1
#   num_primes = [], так как простых чисел ещё нет (они будут добавляться в список)
#   divs_count = 1, так как для получения произведения нужно брать 1
#   twins_count = 0, так как ещё нет простых чисел в разложении числа
F(0, 1, [], 1, 0)

print(*min(ans))  # Выводим минимальное число и его простые делители

Ответ: 17297280 2 3 5 7 11 13

Ошибка.
Попробуйте повторить позже

Задача 12#61485Максимум баллов за задание: 1

Найдите все натуральные числа, принадлежащие отрезку [11 111 111; 77 777 777], у которых ровно $5$ различных делителей. В ответе укажите количество данных чисел.

Показать ответ и решение

По основной теореме арифметики (ОТА) каждое натуральное число, большее 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]$ ).

В данной задаче необходимо, чтобы у числа было ровно 5 различных делителей.

Тогда произведение всех $qi$ должно быть равно 5. Так как число 5 – простое, то только 1 множитель должен быть равен 5. Отсюда некоторое $q = 4 i$ .

Тогда число имеет вид $4 p$ где $p$ – любое простое число.

Таким образом, нужно будет перебрать простые числа так, чтобы получить все возможные числа вида $p4$ из отрезка $[11111111;77777777]$ .

def is_prime(n):  # Функция проверки на простое число
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:  # Если нашли нетривиальный делитель
            return False  # То число не простое, возвращаем False
    return n > 1  # Если число равно 1, то оно непростое, и будет возвращено False, а иначе True


# Нужно перебрать все числа вида x = p**4, где p - простое число
count = 0  # Количество подходящих чисел

# Находим максимально возможное p для отрезка
p_max = int(77_777_777 ** (1 / 4))

# Перебираем простые числа от 2 до максимально возможного
for p in range(2, p_max + 1):
    if is_prime(p):  # Если число p - простое
        # То проверяем, что итоговое число будет принадлежать отрезку
        if 11_111_111 <= p ** 4 <= 77_777_777:
            count += 1

print(count)  # Выводим ответ

Ответ: 8

Ошибка.
Попробуйте повторить позже

Задача 13#61487Максимум баллов за задание: 1

Найдите все натуральные числа, принадлежащие отрезку [ $33$ $333$ $333$ ; $333$ $333$ $333$ ], у которых ровно $3$ различных четных делителя. Общее количество делителей может быть любым. В ответе укажите количество данных чисел.

Показать ответ и решение

По основной теореме арифметики (ОТА) каждое натуральное число, большее 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]$ ).

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

Пусть число имеет следующий вид:

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

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

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

Выпишем количество делителей числа, не содержащих степень числа 2, то есть не являющихся чётными:

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

Из общего количества делителей вычтем количество делителей, не являющихся чётными, и получим количество чётных делителей:

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

Обозначим произведение всех $(qi +1)$ за $m$ . Так как количество по условию должно быть равно $3$ , то $k⋅m = 3$ . Так как число $3$ – простое, то либо $k = 3$ и $m = 1$ , либо $k = 1$ и $m = 3$ .

В первом случае это число $23$ , так как $m = 1$ означает, что других простых чисел в разложении числа нет.

Во втором случае произведение всех $(qi + 1)$ равно $3$ , а значит только один множитель должен быть равен $3$ (так как $3$ – простое число). Отсюда некоторое $qi = 2$ . Поэтому число будет иметь вид $21 ⋅p2$ .

В общем случае это можно представить, как $2 2⋅p ,$ где $p$ – любое простое число (включая число $2$ , что обобщает эти два случая).

Таким образом, нужно будет перебрать простые числа так, чтобы получить все возможные числа вида $2 ⋅p2$ из отрезка $[33333333;333333333]$ .

def is_prime(n):  # Функция проверки на простое число
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:  # Если нашли нетривиальный делитель
            return False  # То число не простое, возвращаем False
    return n > 1  # Если число равно 1, то оно непростое, и будет возвращено False, а иначе True


# Нужно перебрать все числа вида x = 2 * p**2, где p - простое число
ans = 0  # Счётчик для ответа

# Находим максимально возможное p для отрезка
p_max = int(333_333_333 ** (1 / 2))

# Перебираем простые числа от 2 до максимально возможного
for p in range(2, p_max + 1):
    if is_prime(p):  # Если число p - простое
        # То проверяем, что итоговое число будет принадлежать отрезку
        if 33_333_333 <= 2 * p ** 2 <= 333_333_333:
            ans += 1
print(ans)

Ответ: 974

Ошибка.
Попробуйте повторить позже

Задача 14#63212Максимум баллов за задание: 1

Найдите все натуральные числа, принадлежащие отрезку [50000000;60000000], у которых ровно пять различных нечётных делителей (количество чётных делителей может быть любым). В ответе запишите найденные числа в порядке возрастания через пробел.

Показать ответ и решение

По основной теореме арифметики (ОТА) каждое натуральное число, большее 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]$ ).

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

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

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

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

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

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

k 4 x = 2 ⋅p

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

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

import math


def is_prime(n):  # Функция проверки на простое число
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:  # Если нашли нетривиальный делитель
            return False  # То число не простое, возвращаем False
    return n > 1  # Если число равно 1, то оно непростое, и будет возвращено False, а иначе True


# Нужно перебрать все числа вида x = 2**k * p**4, где p - простое число (кроме 2)
ans = []  # Список для сохранения подходящих чисел

# Находим максимально возможное p для отрезка
p_max = int(60_000_000 ** (1 / 4))
# Находим максимальное возможное k для отрезка через логарифм по основанию 2
k_max = int(math.log(60_000_000, 2))

# Перебираем простые числа от 3 до максимально возможного
for p in range(3, p_max + 1):
    if is_prime(p):  # Если число p - простое
        for k in range(k_max + 1):  # Перебираем показатели степени числа 2 с нулевого до максимального
            # Проверяем, что итоговое число будет принадлежать отрезку
            if 50_000_000 <= 2 ** k * p ** 4 <= 60_000_000:
                ans.append(2 ** k * p ** 4)
print(*sorted(ans))

Ответ: 50823362 54700816 55383364 56796482 58492928 59105344 59969536 59973152