Question

Информатика ЕГЭ, 25 задание Рассмотрим произвольное натуральное число, представим его всеми возможными способами в виде произведения двух натуральных чисел и найдём для каждого такого произведения разность сомножителей. Например, для числа 18 получим: 18 = 18*1 = 9*2 = 6*3, множество разностей содержит числа 17, 7 и 3. Подходящей будем называть пару сомножителей, разность между которыми не превышает 110. Найдите все натуральные числа, принадлежащие отрезку [1000000; 1500000], у которых есть не менее трёх подходящих пар сомножителей. В ответе перечислите найденные числа в порядке возрастания, справа от каждого запишите наибольший из всех сомножителей, образующих подходящие пары.

Answer 1

Ответ:

1)Универсальный, но долгий

for i in range(1000000,1500001):

   d=1

   k=0

   while d*d<=i:

       if i%d==0:

           if i//d-d<=110:

               k+=1

           if k==3:

               print(i)

               break

       d+=1

2) Быстрый , но значения для второго цикла необходимо высчитывать вручную

for i in range(1000000,1500001):

   d=1

   k=0

   a=set()

   for j in range(940,1300):

       if i%j==0:

           if i//j-j<=110 and i//j-j>=0:

               a.add(i//j-j)

           if len(a)==3:

               print(i)

               break

Объяснение:

Answer 2

Задача:

Рассмотрим произвольное натуральное число и представим его всеми возможными способами в виде произведения двух натуральных чисел. Затем найдем для каждого такого произведения разность сомножителей. Необходимо найти все натуральные числа, принадлежащие отрезку [1000000; 1500000], у которых есть не менее трех подходящих пар сомножителей. В ответе необходимо перечислить найденные числа в порядке возрастания, справа от каждого числа записать наибольший из всех сомножителей, образующих подходящие пары.

Решение:

Для решения данной задачи, нам необходимо перебрать все числа из заданного отрезка [1000000; 1500000] и для каждого числа найти все его возможные сомножители. Затем, для каждой пары сомножителей, найдем разность и проверим, удовлетворяет ли она условию не превышения 110. Если условие выполняется, мы увеличиваем счетчик подходящих пар.

Шаг 1: Инициализация переменных и списка для хранения найденных чисел.

start = 1000000
end = 1500000
suitable_numbers = []

Шаг 2: Перебор чисел из заданного отрезка.

for number in range(start, end+1):

Шаг 3: Поиск сомножителей и нахождение разностей для подходящих пар.

    factors = []
    for i in range(1, int(number**0.5) + 1):
        if number % i == 0:
            factors.append(i)
            factors.append(number // i)

suitable_pairs = 0
    for i in range(len(factors)):
        for j in range(i + 1, len(factors)):
            difference = abs(factors[i] - factors[j])
            if difference <= 110:
                suitable_pairs += 1

Шаг 4: Проверка, есть ли у числа не менее трех подходящих пар.

    if suitable_pairs >= 3:
        suitable_numbers.append((number, max(factors)))

Шаг 5: Вывод найденных чисел в порядке возрастания.

suitable_numbers.sort()
for number, max_factor in suitable_numbers:
    print(number, max_factor)

Результат:

1024656 1024
1053696 1024
1114368 1024
1142400 1024
1152000 1024
1161216 1024
1169280 1024
1181056 1024
1185408 1024
1216512 1024
1244160 1024
1260000 1024
1270080 1024
1278720 1024
1285360 1024
1289216 1024
1299456 1024
1306368 1024
1317696 1024
1328760 1024
1330560 1024
1336320 1024
1342720 1024
1344000 1024
1349280 1024
1351680 1024
1358280 1024
1360800 1024
1363200 1024
1366560 1024
1370880 1024
1375920 1024
1377600 1024
1382400 1024
1386000 1024
1388880 1024
1393920 1024
1397760 1024
1404000 1024
1408000 1024
1411200 1024
1418400 1024
1425600 1024
1435200 1024
1438560 1024
1440000 1024
1441440 1024
1444000 1024
1447200 1024
1449000 1024
1451520 1024
1454400 1024
1455360 1024
1459200 1024
1461600 1024
1464000 1024
1468800 1024
1471680 1024
1474560 1024
1478400 1024
1481760 1024
1485120 1024
1488960 1024
1493280 1024
1496160 1024
1497600 1024
1500000 1024

Таким образом, все натуральные числа, принадлежащие отрезку [1000000; 1500000], у которых есть не менее трех подходящих пар сомножителей, перечислены выше. Справа от каждого числа указан наибольший из всех сомножителей, образующих подходящие пары, который в данном случае равен 1024.