Е25.52 представленные в виде произведения ровно двух простых множителей

Администратор

3 месяца назад

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

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

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

ЕГКР по информатике 18 апреля 2026 – задание №25

Показать решение...

Решение:

Решение на Python

def prosto(n):
    for i in range(2, int(n**0.5)+1):
        if n%i==0:
            return False
    return True
def mnoj(n):
    s=[]
    d=2
    while n>1:
        if n%d==0:
            s.append(d)
            n=n//d
        else:
            d+=1
    return s
for i in range(8_996_453, 10_000_000):
    m=mnoj(i)
    if len(m)==2 and prosto(m[0]) and prosto(m[1]) and m[0]*m[1]==i:
        if str(m[0]).count('3')==2 and str(m[1]).count('3')==2:
            print(i, max(m))

def prosto(n):

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

if n%i==0:

return False

return True

def mnoj(n):

s=[]

d=2

while n>1:

if n%d==0:

s.append(d)

n=n//d

else:

d+=1

return s

for i in range(8_996_453, 10_000_000):

m=mnoj(i)

if len(m)==2 and prosto(m[0]) and prosto(m[1]) and m[0]*m[1]==i:

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

print(i, max(m))

Код по смыслу близок, но он будет работать очень медленно: тут перебираеться каждое число от 8_996_453 до 10_000_000 и раскладываеться его на множители.

Здесь удобнее идти от простых множителей, потому что по условию число должно быть произведением ровно двух простых чисел, и у каждого из них в записи ровно две цифры 3

Вот более удачное решение:

def prime(n):
    if n < 2:
        return False
    d = 2
    while d * d <= n:
        if n % d == 0:
            return False
        d += 1
    return True

p = []

# собираем все простые числа, у которых ровно две цифры 3
for x in range(2, 100000):
    if str(x).count('3') == 2 and prime(x):
        p.append(x)

ans = []

# составляем произведения двух таких простых чисел
for i in range(len(p)):
    for j in range(i, len(p)):
        n = p[i] * p[j]
        if n > 8_996_452:
            ans.append((n, max(p[i], p[j])))

ans.sort()

for x in ans[:5]:
    print(x[0], x[1])

def prime(n):

if n < 2:

return False

d = 2

while d * d <= n:

if n % d == 0:

return False

d += 1

return True

p = []

# собираем все простые числа, у которых ровно две цифры 3

for x in range(2, 100000):

if str(x).count('3') == 2 and prime(x):

p.append(x)

ans = []

# составляем произведения двух таких простых чисел

for i in range(len(p)):

for j in range(i, len(p)):

n = p[i] * p[j]

if n > 8_996_452:

ans.append((n, max(p[i], p[j])))

ans.sort()

for x in ans[:5]:

print(x[0], x[1])

Ответ:

9001609 24133
9002887 38639
9006149 38653
9012167 3853
9012373 23531