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

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

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

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 =[1] + [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 = 179424695;
  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;
}

Печать