Найдите количество пятизначных чисел, взаимно простых с числом 92.
Два числа называются взаимно простыми, если они не имеют общего натурального делителя, кроме 1. Иными словами, их наибольший общий делитель равен 1.
Найдите количество пятизначных чисел, взаимно простых с числом 92.
Все пятизначные числа лежат в интервале
[10 000; 100 000)
или
[10 000; 99 999]
И всего их 90 000 шт.
Число 92 представляет собой произведение простых чисел:
2 * 2 * 23
Таким образом, необходимо, чтобы пятизначные числа не делились на 2 и не делились на 23 по отдельности. Делаем укороченное решето Эратосфена, вычёркивая кратные только этим двум числам.
Чтобы соблюсти первое условие, убираем все чётные числа, остаётся 45 000 чисел.
Из этой оставшейся нечётной половины каждое 23-е делится на 23 (т.е. разница между соседними - 46). Это числа, дающие остаток 23 при делении на 46. Осталось найти точное количество таких чисел.
Минимальное число:
(10 000 + 22) div 46 * 46 + 23 = 10 005 = 435 * 23
Максимальное число:
(99 999 + 22) div 46 * 46 - 23 = 99 981 = 4 347 * 23
Всего чисел:
(4 347 - 435) / 2 + 1 = 1 957
Остаётся вычесть это из 45 тыс нечётных чисел, и получим:
45 000 - 1 957 = 43 043
Если нужно искать программой, то закодим вышеприведённые формулы в слегка упрощённом виде:
lo, hi = 10_000, 99_999
lo23, hi23 = (lo + 22) // 46 * 2 + 1, (hi + 22) // 46 * 2 - 1
print((hi - lo + 1) // 2 - (hi23 - lo23) // 2 - 1)
Чтобы найти количество пятизначных чисел, взаимно простых с числом 92, мы можем использовать принцип включения-исключения.
Сначала посчитаем количество всех пятизначных чисел. Всего пятизначных чисел равно разности между наибольшим и наименьшим пятизначными числами плюс 1:
99999 - 10000 + 1 = 90000.
Затем посчитаем количество пятизначных чисел, которые делятся на 2 или 23 (поскольку 92 = 2 * 2 * 23). Чтобы это сделать, мы разделим 90000 на 2 и 23, затем сложим результаты и вычтем количество чисел, которые делятся на оба числа (то есть на 2 * 23 = 46):
90000/2 + 90000/23 - 90000/46 = 45000 + 3913 - 1956 = 47057.
Таким образом, количество пятизначных чисел, взаимно простых с числом 92, равно:
90000 - 47057 = 42943.