Задачка из ЕГЭ по информатике

Question

Подскажите, как решаются подобные задачки?

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

Например, в диапазоне [5; 9] ровно два различных натуральных делителя имеют числа 6 и 8, поэтому для этого диапазона вывод на экране должна содержать следующие значения:

2 3

2 4

Мой код:

a = 174457
b = 174505
k = 0
d = []
for n in range(a, b+1):
    if n%2 == 0:
        k+=1
        d.append(n)
        if k > 2:
            break
    if k == 2:
        print(d[0], d[1])

А вот решение на паскале (в ответах только такое):

var 
    x, numDel, i, j: longint;
    d: array[1..2] of longint;
begin
    for i := 174457 to 174505 do begin
        numDel := 0;
        for j := 2 to i div 2 do begin
            if i mod j = 0 then begin
                numDel := numDel + 1;
                if numDel > 2 then break;
                d[numDel] := j;
            end;
        end;
        if numDel = 2 then writeln(d[1], ' ', d[2]);
    end;
end.

Answer 1

по идее можно сделать следующее (как мне кажется):

из условия очевидно, что искомые числа являются или

произведением двух взаимно простых чисел (НОД(a, b) = 1)

кроме того очевидно, что максимально-возможное число из пары может быть только 174505 / 2

или произведение простого числа и квадрата этого же простого числа

значит простое число не может превышать кубического корня из от 174505, т.е. 56

отсюда что я бы сделал (правда это решение сугубо в лоб)

подзадача 2) решает очень просто - надо всего лишь перебрать все простые числа до 53 (это очень просто)

подзадача 1) решается через

# пройтись по всем числам
for i in range(2, 174505 // 2):
    # пройтись по всему диапазону произведений двух чисел i и j
    for p in range(174457, 174505 + 1):
        # если число не делится на i - не рассматриваем (значит j не существует)
        if p % i != 0:
            continue

        # определяем второе число из произведения
        j = p // i

        # вычисляем НОД (можно взять функцию питона gcd) и сравниваем с 1

БЛОГ НА HUSL

Задачка из ЕГЭ по информатике

Ответы (1 шт):