Задача к ЕГЭ по информатике на тему «делители числа» №2

Просмотров 7 Комментарии 0

Найти на промежутке $[21321,99999]$ числа, у которых ровно 2 различных нетривиальных делителя. Найдите наибольшие 5 подходящих чисел и минимальный нетривиальный делитель каждого числа. В ответ запишите найденные 5 чисел в порядке убывания и делитель каждого из чисел в таком порядке:

Число1, Дел1; Число2, Дел2; и т.д. (После каждой запятой или точки с запятой ставится пробел, каждая группа (число и его минимальный делитель) отделяется от следующей группы точкой с запятой, после последней группы никакой знак не ставится).

def divs(x): # функция возврающая список делителей числа
    d = set()
    for i in range(2,int(x**0.5)+1):
        if x % i == 0:
            d.add(i)
            d.add(x//i)
        if len(d) > 2: # для оптимизации возращаем список делителей если кол-во делителей больше 2
            return sorted(d)
    return sorted(d)

count = 0
for x in range(99999,21321,-1): # для оптимизации начинаем перебор с большего к меньшему
    d = divs(x)
    if len(d) == 2:
        print(x,d[0]) # вывод ответа
        count += 1
        if count == 5:
            break

Ответ: 99998, 2; 99993, 3; 99987, 3; 99986, 2; 99985, 5