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

Простые числа_файлы и не только

Создаем решето

from time import process_time as prt
N = 10000000
t0 = prt()
A = [0, 0] + [1]*(N-1)
k = 2
while k * k <= N :
    if A[k]:
        for i in range (k*k, N+1, k): A[i] = 0
    k += 1
S =[1] + sorted({i for i in range(N+1) if A[i]})

print(prt() - t0)
print(*S[:20])

from time import process_time as prt
t0 = prt()
fname = 'pr_10000000.ch'
pr = [int(s) for s in open(fname)]
print(len(pr),prt() - t0)
A, Z = [0] *10, [0]*10
AZ = []
for x in pr :
  y = int(str(x)[::-1])
  a =int(str(x)[0])
  z =int(str(x)[-1])
  A[a] += 1
  Z[z] += 1
  if x == y : AZ.append(x)
  
print(*[(i, int(A[i]*1000/len(pr))) for i in range(10)])  
print(*[(i, int(Z[i]*1000/len(pr))) for i in range(10)])  
print(len(AZ))
print(AZ[-20])

import sympy as sp
A =[1331931112737933997, 3779191112737713317, 3933337112731319333, 9197337112731317119, 7979399112793339739]
x = A[0]
y = sp.ispryme(x)
print(x,y)

# Эффективное решето
def resheto(N):
    a=[False,False,True]+[True, False]*(N//2)
    i=3
    ii = 9
    while ii < N:
        for j in range(ii,N,i): a[j] = [False];
        i += 2
        ii = i *i
    return a
N=8**5
a = resheto(N)
for s in[*open(0)][1:]:
    d=int(s);
    i=a.index(True,d+1);
    print(i*a.index(True,i+d))

# Эффективное решето
def resheto(N):
    a=[False,False,True] + [True,False]*(N//2)
    i=3
    while i*i<N:
        if a[i] :
          a[i*i:N:i]=[False]*-(-N//i+i);
        i += 2
    return a
N=8**5
a = resheto(N)
for s in[*open(0)][1:]:
    d=int(s);
    i=a.index(True,d+1);
    print(i*a.index(True,i+d))

Решето Эратосфена. Вариант А			Решето Эратосфена. Вариант А
def r_A(N): M = [1]N d = 2 while d d <= N : for j in range( d * d, N, d): M[j] = 0 d += 1 return M			def r_B(N): M = [1]N i = 2 while i i < N: M[ii:N:i]=[0]-(-N//i + i); i += 1 return M
N	time A	time B	time A/ time B	Память A (пик) MB	Память B (пик) MB
10**5	0.06	0.016	3.75	0.79	1.53
10**6	0.55	0.11	5	7.66	15.26
510*6	4.48	0.76	5.89	38.18	76.3
10**7	9.78	1.75	5.58	76.29	152.59
510*7	58.0	11.2	5.17	381.47	762.94
10**8	126.8	25.8	4.91	762.94	1525.88

Прикрепленные файлы
pr_1000000.ch
pr_10000000.ch

Печать