Задание 25. Информатика. ЕГЭ. Поляков-2600

Просмотры: 297
Изменено: 24 ноября 2024

Среди целых чисел, принадлежащих числовому отрезку \([268312; \,\, 336492]\), найдите числа, которые представляют собой произведение двух различных простых делителей. Запишите в ответе количество таких чисел и минимальное их них.

Решение:

Python


def sieve(N):
    a = [1]*(N+1)

    a[0] = 0
    a[1] = 0

    for x in range(2, int(N**0.5) + 1):
        if a[x]:
            for i in range(x**2, N+1, x):
                a[i] = 0
                
    primes = []
    for x in range(2, N+1):
        if a[x]:
            primes.append(x)
    
    return primes

primes = sieve(336492)
a = []

for x in range(268312, 336493):
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            sec_div = x // i
            if i in primes and i != sec_div and sec_div in primes:
                a.append(x)
            break

print(len(a), min(a))

Ответ: \(14380 \,\, 268313\)