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

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

 

Решето Эратосфена — алгоритм нахождения всех простых чисел до некоторого целого числа 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();
}

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


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

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

  • переписал этот текст на собственный язык 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]);
            }
          }
        }

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

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


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

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

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


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

Ваш e-mail не будет опубликован. Обязательные поля помечены *