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

Решето Эратосфена

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

from time import process_time as prt
N = 15801580
M = 1000000
t0 = prt()
A = [False, False] + [True]*(N-1)
k = 2

while k * k <= N :
    if A[k]:
        for i in range (k*k, N+1, k): A[i] = False
    k += 1
S =[i for i in range(N+1) if A[i]]

print(prt() - t0)
print(len(S), S[1000000], S[-5:])

#include <iostream>
#include <vector>
#include <ctime>

using namespace std;

int main()
{
  clock_t start = clock();
  int n = 15801580;
  vector <bool> M(n, true);
  M[0] = false;  M[1] = false;
  for (int i = 2; i < n; i += 2){M[i] = false;};
  int p = 3;
  while (p * p < n ){
    if (M[p]) {
      for (int i = p * p; i < n; i += p){M[i] = false;}
    }
    p += 2;
  }
  vector<int> Pr;
  Pr.push_back(0);
  for (int i = 0;  i < n; i++){
    if (M[i]) {Pr.push_back(i);}
  }
  int k = Pr.size();
  //for (int i = k - 5;  i < k; i++){cout<<i<<'='<<Pr[i]<<endl;}
  cout<< clock() - start;
  return 0;
}

#include <iostream>
#include <vector>

using namespace std;
//using ll = long long;

int main()
{
  int n = 158015;
  int k = 100  ;
  vector <bool> M(n, true);
  M[0] = false;  M[1] = false;
  vector<int> Pr(k);
  for (int p = 2; p < n; p++) {
    if (M[p]) {
      for (int i = p * p; i < n; i += p){M[i] = false;}
    }
  }
  int j = 0;
  for (int i = 2; i < n and j < k-1; i++){
    if (M[i]==true){ j++; Pr[j] = i;}
  }
  for (int i = k -5 ; i < k; i++){cout<<i<<'='<<Pr[i]<<endl;}
  cout<<"Ok";
  return 0;
}

#reheto
def sieve_eratosfen (N):
    A = [False, False, True] + [True, False]*(N//2)
    kk = 2
    while kk * kk < N : kk += 1
    k = 3
    while k <=  kk :
        if A[k]:
            for i in range (k*k, N+1, k): 
                A[i] = False
        k += 2
    return [2] + [i for i in range(3, N+1, 2) if A[i]]

def mindel(n):
   if n % 2 == 0 : return 2
   if n < 9 : return n
   p = 3
   while (n % p != 0) and (p * p < n) : p+=2
   if p * p > n : p = n
   return p

def fact(n):
  F = {}
  while n > 1 :
    d = mindel(n)
    k = 0
    while n % d == 0 :
      k += 1
      n = n // d
    F[d] = k
  return F  

def check(n,P):
    s = str(n)
    k = len(s)//2
    a = int(s[:k])
    b = int(s[k:])
    if (s[k] != '0') and (a in P) and (b in P) : return a, b
    return 0 , 0               
    

from time import process_time as prt
import sympy as sp

#A, B = 3_000_000, 4_999_999
#A, B = 15000000, 15801580
#A, B = 175600000, 177500000

A, B = map(int,input().split())

t0 =prt()
Pr = sieve_eratosfen (B)
Spr = set(Pr)
l, r = 0,len(Pr)
while r - l > 1 :
    m = (r + l) // 2
    if Pr[m] < A : l = m
    else: r = m
print(f'Resheto: {len(Pr)=} Pr[{l}]={Pr[l]} Pr[{r}]={Pr[r]}')
cnt = 0
ans = 0
kk = 0
for n in Pr[r:]:
    kk += 1
    a, b = check(n,Spr)
    if a == 0 : continue
    cnt += 1
    x = a * b
    if x > ans :
        ans = x
        n_ans = n
    #print(f'{n}, {a} * {b} = {a*b}')
print(f'[{A};{B}]\n {cnt=} {ans=} {n_ans} {kk=} {(prt() - t0)=}')

#perebor
def sieve_eratosfen (N):
    A = [False, False, True] + [True, False]*(N//2)
    kk = 2
    while kk * kk < N : kk += 1
    k = 3
    while k <=  kk :
        if A[k]:
            for i in range (k*k, N+1, k): 
                A[i] = False
        k += 2
    return [2] + [i for i in range(3, N+1, 2) if A[i]]

def mindel(n):
   if n % 2 == 0 : return 2
   if n < 9 : return n
   p = 3
   while (n % p != 0) and (p * p < n) : p+=2
   if p * p > n : p = n
   return p

def fact(n):
  F = {}
  while n > 1 :
    d = mindel(n)
    k = 0
    while n % d == 0 :
      k += 1
      n = n // d
    F[d] = k
  return F  

def check(n,P):
    s = str(n)
    k = len(s)//2
    a = int(s[:k])
    b = int(s[k:])
    if (s[k] != '0') and (a in P) and (b in P) : return a, b
    return 0 , 0               
    

from time import process_time as prt
import sympy as sp
#A, B = 15000000, 17000000
#A, B = 15800_00000, 15850_00000
A, B = 1580_12345, 1583_15800

#A, B = map(int,input().split())
t0 = prt()
ll = len(str(A))
la, lb= ll//2, (ll+1)//2
aa, ab = int(str(A)[:la]), int(str(B)[:la])
bb = 10**lb - 1
Pr= []
for n in range(2,bb+1):
    d = mindel(n)
    if d == n :
        Pr.append(n)
#Pr = sieve_eratosfen (bb)
Ap = [p for p in Pr if aa <= p <= ab]
Bp = [p for p in Pr if len(str(p)) == lb]

#Spr = set(Pr)
print(f'Perebor: {la=} {lb=}\n{aa=} {ab=}\n{len(Ap)=} {len(Bp)=} {Bp[-1]=}')
cnt = 0
ans = 0
kk = 0
for an in Ap:
    for bn in Bp :
        n = int(str(an) + str(bn))
        if n < A or n > B : continue
        kk += 1
        d = mindel(n)
        if d < n : continue
        cnt += 1
        c = an * bn
        if c > ans :
          ans = max(ans, an * bn)
          n_ans = n
          #print(f'{n=} {ans=}')
        
print(f'[{A};{B}]\n {cnt=} {ans=} {n_ans=} {kk=} {(prt() - t0)=}')    
#'''

# temp
def sieve_eratosfen (N):
    A = [False, False, True] + [True, False]*(N//2)
    kk = 2
    while kk * kk < N : kk += 1
    k = 3
    while k <=  kk :
        if A[k]:
            for i in range (k*k, N+1, k): 
                A[i] = False
        k += 2
    return [2] + [i for i in range(3, N+1, 2) if A[i]]

def mindel(n):
   if n % 2 == 0 : return 2
   if n < 9 : return n
   p = 3
   while (n % p != 0) and (p * p < n) : p+=2
   if p * p > n : p = n
   return p

def fact(n):
  F = {}
  while n > 1 :
    d = mindel(n)
    k = 0
    while n % d == 0 :
      k += 1
      n = n // d
    F[d] = k
  return F  

def check(n,P):
    s = str(n)
    k = len(s)//2
    a = int(s[:k])
    b = int(s[k:])
    if (s[k] != '0') and (a in P) and (b in P) : return a, b
    return 0 , 0               
    

from time import process_time as prt
import sympy as sp
Data = []
for k in range (1,100):
    p =sp.prime(k * 10**5)
    Data.append(p)
    #print(f'{k}\t{k * 10**6}\t{p:_}')
A, B = Data[-2], Data[-1]
print(f'[{A};{B}]')    
'''
Pr = sieve_eratosfen (B)
Spr = set(Pr)
l, r = 0,len(Pr)
while r - l > 1 :
    m = (r + l) // 2
    if Pr[m] < A : l = m
    else: r = m
print(f'{len(Pr)=} Pr[{l}]={Pr[l]} Pr[{r}]={Pr[r]}')
cnt = 0
ans = 0
for n in Pr[r:]:
    a, b = check(n,Spr)
    if a == 0 : continue
    cnt += 1
    ans = max(ans, a * b)
    #print(f'{n}, {a} * {b} = {a*b}')
print(f'[{A};{B}]\n {cnt=} {ans=}')    
#'''

#per_resh
def sieve_eratosfen (N):
    # реализация Решета Эратосфена
    A = [False, False, True] + [True, False]*(N//2)
    kk = 2
    while kk * kk < N : kk += 1
    k = 3
    while k <=  kk :
        if A[k]:
            for i in range (k*k, N+1, k): 
                A[i] = False
        k += 2
    return [2] + [i for i in range(3, N+1, 2) if A[i]]

def mindel(n):
   # Поиск минимального делителя числа
   if n % 2 == 0 : return 2
   if n < 9 : return n
   p = 3
   while (n % p != 0) and (p * p < n) : p+=2
   if p * p > n : p = n
   return p
   


#A, B = 87690_12345, 87691_23450
A, B = map(int,input().split())
ll = len(str(A))
la, lb= ll//2, (ll+1)//2
aa, ab = int(str(A)[:la]), int(str(B)[:la])
bb = 10**lb - 1
Pr = sieve_eratosfen (bb)
Ap = [p for p in Pr if aa <= p <= ab]
Bp = [p for p in Pr if len(str(p)) == lb]
cnt = 0
ans = 0
print(f'{Bp=}')
print(f'{Pr=}')

for an in Ap:
    for bn in Bp :
        n = int(str(an) + str(bn))
        if n < A or n > B : continue
        d = mindel(n)
        if d < n : continue
        cnt += 1
        c = an * bn
        print(n, an, bn)
        if c > ans :
          ans = max(ans, an * bn)
print(f'{cnt}\n{ans}')    
#'''

Печать