Задание 25 (ЕГЭ по информатике) поиск чисел, которые являются степенью простого числа с натуральным показателем степени, большим 1

 Задача (№ 25, ЕГЭ по информатике)

Напишите программу, которая перебирает целые числа, большие 700 000, в порядке возрастания и ищет среди них такие, которые являются степенью простого числа с натуральным показателем степени, большим 1.
В ответе в первом столбце таблицы запишите первые 5 найденных чисел в порядке возрастания, а во втором столбце - для каждого из чисел соответствующие им простое число.

Например, число 27 = 3³

Количество строк в таблице для ответа избыточно.

Алгоритм решения

1. Перебираем числа, начиная с 700 001.

2. Для каждого числа находим его разложение на простые множители с учётом кратности (функция f(n)).

3. Проверяем два условия:

   • Количество множителей в разложении больше 1 (показатель степени > 1).

   • Все множители одинаковые (число является степенью одного простого числа).

4. Как только находим 5 таких чисел, завершаем перебор.

Программа решения задачи на языке Python

def f(n):
    d = []
    for k in range(2, int(n**0.5) + 1):
        while n % k == 0:
            d.append(k)
            n //= k
    if n > 1:
        d.append(n)
    return d

k = 0
x = 700001
while k != 5:
    y = f(x)
    y1 = set(y)
    if len(y) > 1 and len(y1) == 1:
        print(x, y[0])
        k += 1
    x += 1

Пояснения

• Функция f(n) возвращает список простых делителей числа $n$ (например, для числа 72 → [2, 2, 2, 3, 3]).

• y1 = set(y) оставляет только уникальные делители. Если все делители одинаковые, длина множества будет равна 1.

• Условие len(y) > 1 гарантирует, что показатель степени больше 1.

Результат выполнения программы

703921 839

704969 89

707281 29

727609 853

734449 857

ЕГЭ по информатике. Задание 25. Поиск чисел, представленных в виде произведения ровно двух простых множителей, не обязательно различных

Задача. Напишите программу, которая перебирает целые числа, большие 6 651 220, в порядке возрастания и ищет среди них числа, представленные в виде произведения ровно двух простых множителей, не обязательно различных, каждый из которых содержит в своей записи ровно одну цифру 2.

В ответе в первом столбце таблицы запишите первые 5 найденных чисел в порядке возрастания, а во втором столбце - для каждого из чисел соответствующий им наибольший из найденных множителей.

Источник: kompege.ru

Пример числа:

Число 6651241 можно разложить на 2579 × 2579, и оба этих множителя — простые числа, содержащие ровно одну цифру "2".

Напишем функцию, которая возвращает список простых множителей, в виде произведения которых можно представить заданное натуральное число.

def f(n):

    a = []

    for k in range(2,int(n**0.5)+1):

        while n%k==0:

            a.append(k)

            n//=k

    if n>1:

        a.append(n)

    return a

• В цикле для k от 2 до √n: пока число n делится на k, добавляем число k в список множителей.

• После разложения, если n > 1, значит, оно простое и его тоже добавляем в список.

Проверяем работу функции

print(f(12)) # вывод [2, 2, 3]

print(f(424)) # вывод [2, 2, 2, 53]

print(f(6889)) # вывод [83, 83]

print(f(17)) # вывод [17]

Решаем задачу

p = 0  # Счётчик найденных чисел

x = 6_651_220 + 1  # Начинаем с числа после 6 651 220

while p != 5:

    y = f(x) # Получаем список множителей для числа x

    if len(y) == 2:  # Если у числа x ровно два простых множителя

        # Проверяем, что в каждом множителе ровно одна цифра "2"

        if str(y[0]).count('2') == 1 and str(y[1]).count('2') == 1:

            print(x, max(y))  # Выводим число и наибольший множитель

            p += 1

    x += 1  # Переходим к следующему числу

Вывод:

6651241 2579

6651262 3325631

6651286 3325643

6651314 3325657

6651347 289189

Идет невисокосный год. Сколько дней до Нового года?

 Задача. Пусть идет невисокосный год. Сколько дней до Нового года? 

Сохраним количество дней в каждом месяце в списке days.

Применим срезы по-новогоднему :)

Программа на Python

print('Год не високосный. Сколько дней до Нового года? Введите текущие')

m = int(input('месяц: '))

d = int(input('день: '))

days = [31,28,31,30,31,30,31,31,30,31,30,31]

print('До Нового года: ',sum(days[m-1:])- d + 1,' дн.')

Еще бы выводить сообщение об ошибочных данных, если пользователь введет не то, что нужно (допишем еще)

Запуск на текущий момент 

Год не високосный. Сколько дней до Нового года? Введите текущие

месяц: 1

день: 3

До Нового года:  363  дн.