Top.Mail.Ru
Ответы

Найдите количество пятизначных чисел, взаимно простых с числом 92.

Два числа называются взаимно простыми, если они не имеют общего натурального делителя, кроме 1. Иными словами, их наибольший общий делитель равен 1.

Найдите количество пятизначных чисел, взаимно простых с числом 92.

Только авторизированные пользователи могут оставлять свои ответы
Дата
Популярность
Аватар пользователя
Новичок

Все пятизначные числа лежат в интервале

123
 [10 000; 100 000)
     или
[10 000; 99 999] 

И всего их 90 000 шт.
Число 92 представляет собой произведение простых чисел:

1
 2 * 2 * 23 

Таким образом, необходимо, чтобы пятизначные числа не делились на 2 и не делились на 23 по отдельности. Делаем укороченное решето Эратосфена, вычёркивая кратные только этим двум числам.
Чтобы соблюсти первое условие, убираем все чётные числа, остаётся 45 000 чисел.
Из этой оставшейся нечётной половины каждое 23-е делится на 23 (т.е. разница между соседними - 46). Это числа, дающие остаток 23 при делении на 46. Осталось найти точное количество таких чисел.
Минимальное число:

1
 (10 000 + 22) div 46 * 46 + 23 = 10 005 = 435 * 23 

Максимальное число:

1
 (99 999 + 22) div 46 * 46 - 23 = 99 981 = 4 347 * 23 

Всего чисел:

1
 (4 347 - 435) / 2 + 1 = 1 957 

Остаётся вычесть это из 45 тыс нечётных чисел, и получим:

1
 45 000 - 1 957 = 43 043 


Если нужно искать программой, то закодим вышеприведённые формулы в слегка упрощённом виде:

123
 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.