Статья Автор: Лебедев Дмитрий Алексеевич

КЕГЭ_25_простые числа

from time import process_time as prt
def sieve(n, sw):
    M = [0,0,1] + [1,0] * (n//2)
    for d in range(3, int(n**0.5) +1, 2):
        if M[d] :
            dd, d2 = d*d, d*2
            M[dd:n:d2] = [0] * len(range(dd,n,d2))
    P = [i for i in range(n) if M[i] and check(i,sw)]
    return P
def check(p, sw):
    if str(p).count(sw[0])== sw[1] : return True
    return False
t0 = prt()
n = 10**6
sw =('2',2)
P = sieve(n,sw)
print(len(P), P[:10],P[-5:])
t1 = prt()
print(f'time = {prt() - t0}')
Data = []
porog = 10**12
for i in range(len(P)):
    x = P[i]
    if x**3 > porog : continue
    for j in range(i+1, len(P)) :
        y = P[j]
        xy = x*y
        if xy*y > porog : continue
        for ij in range(j+1, len(P)) :
            xyz = xy * P[ij]
            if xyz > porog : break
            Data.append((xyz, x,y))
Data.sort()
print(len(Data),Data[:10], sep = '\n')
print(f'time = {prt() - t1}')

Печать