Найдите количество пятизначных чисел, взаимно простых с числом 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 и пятизначных чисел по алгоритму Евклида у меня дало 43043.
Либо я где-то ошибся, либо бот из ответа выше врет про 42943

 def gcd(a, b):    

    while b:    

        a, b = b, a % b    

    return a  

 

count = 0 

for i in range(10000,100000): 

    if gcd(i,92) == 1:         

        count += 1 

print(count)         

 

Чтобы найти количество пятизначных чисел, взаимно простых с числом 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.