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

Задачи и их решения / Решето Эратосфена

 

Решето Эратосфена — алгоритм нахождения всех простых чисел до некоторого целого числа N, который приписывают древнегреческому математику Эратосфену Киренскому. Название алгоритма говорит о принципе его работы, то есть решето подразумевает фильтрацию, в данном случае фильтрацию всех чисел за исключением простых. По мере обработки массива чисел нужные числа (простые) остаются, а ненужные (составные) исключаются.

Сама проблема получения простых чисел занимает ключевое место в математике, на ней основаны некоторые криптографические алгоритмы, например RSA.

Для нахождения всех простых чисел не больше заданного числа N нужно выполнить следующие шаги:

  • Заполнить массив из N элементов целыми числами подряд от 2 до N.
  • Присвоить переменной p значение 2 (первого простого числа).
  • Удалить из массива числа от p2 до N с шагом p (это будут числа кратные p: p2, p2+p, p2+2p и т. д.).
  • Найти первое неудаленное число в массиве, большее p, и присвоить значению переменной p это число.
  • Повторять два предыдущих шага пока это возможно.

Все оставшиеся в массиве числа являются простыми числами от 2 до N

На рисунке проиллюстрирован алгоритм поиска простых чисел. Числа, отмеченные белым, являются удаленными.
Решето Эратосфена

 
Реализация на C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
int main()
{
  int n;
  cout << "n= ";
  cin >> n;
  int *a = new int[n + 1];
  for (int i = 0; i < n + 1; i++)
    a[i] = i;
  for (int p = 2; p < n + 1; p++)
  {
    if (a[p] != 0)
    {
      cout << a[p] << endl;
      for (int j = p*p; j < n + 1; j += p)
        a[j] = 0;
    }
  }
  cin.get(); cin.get();
}

 
Результат выполнения
Решето Эратосфена


Назад: Задачи и их решения

Комментариев к записи: 14

  • переписал этот текст на собственный язык PPL, при n=100000 программа упала при значении 46349. Откомпилировал и запустил оригинал на cpp - тот же результат - последнее простое число 46349. проблема во внутреннем цикле, когда индекс выходит за границы массива. Нужен отлаженный код для проверки языка PPL

    • Елена Вставская
      Видимо, это последнее простое число в 2-байтной разрядной сетке (до 65535)

      • // сделал исправления в вашем коде, не выходит за границы массива и не падает, // написал на C#
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        32
        using System;
        namespace erat1
        {
          class Program
          {
            static void Main(string[] args)
            {
              int n = 10000;
              int len = n + 1;
              int[] primes = new int[len];
              for (int i = 0; i < len; i++)
                primes[i] = i;

              for (int i = 2; i < len; i++)
              {
                for (int j = i + 1; j < len; j++)
                {
                  if (primes[j] == 0)
                    continue;
                  if (j % i == 0)
                  {
                    primes[j] = 0;
                    continue;
                  }
                }
              }
              for (int i = 0; i < len; i++)
                if(primes[i] != 0)
                  Console.WriteLine(primes[i]);
            }
          }
        }

        • 1
          2
          3
          4
          5
          6
          7
          8
          9
          10
          11
          12
          13
          14
          15
          16
          17
          18
          19
          20
          21
          22
          23
          24
          25
          26
          27
          28
          29
          /*Тот же самый код на с++ с небольшой, но очень значимой оптимизацией
          на 100000 не падает.
          */

          #include<iostream>
          using namespase std;

          int main() {
              int n;
              vector<int> v;
              cin >> n;
          //заполняем вектор
              for(int i = 0; i <= n; i++) v.push_back(i);
          //обработка
              for(int i = 2; i <= n; i++) {
                  for(int j = i + 1; j <= n; j++) {
                      if(v[j] == 0) continue;
                      if(j % i == 0) {
                          v[j] = 0;
                          continue;
                      }
                  }
                  if(i * i > n) break// <== ОПТИМИЗАЦИЯ
              }
          //вывод на печать
              for(int s : v) {
                  if(s != 0) cout << s << '\n';
              }
          return 0;
          }

  • Vladimir Khludenkov
    А если надо найти n-е по счёту число этим способом? Мы же не знаем изначально, сколько чисел для просеивания надо брать? Если делать частями, то мы не знаем, с какого места просеивать последующие "куски" выборок.

  • Жмых Пажилой
    Есть ли какой-нибудь похожий алгоритм для полупростых чисел?


  • Шахноза
    А как можно реализовать использование не всех чисел, а только нечетных, и среди нечетных уже искать простые?

  • Наталья
    Не могу понять 8 рядок. Понимаю, что описывается массив. Подскажите, пожалуйста!

    • Елена Вставская
      n - это число, до которого ищутся простые числа. В строке 8 выделяется память под n+1 целое число


Добавить комментарий

Ваш адрес email не будет опубликован.