«

»

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

Вполне вероятно, что алгоритм, придуманный более 2000 лет назад греческим математиком Эратосфеном Киренским, был первым в своем роде. Его единственная задача – нахождение всех простых чисел до некоторого заданного числа N. Термин «решето» подразумевает фильтрацию, а именно фильтрацию всех чисел за исключением простых. Так, обработка алгоритмом числовой последовательности оставит лишь простые числа, все составные же отсеются.

Рассмотрим в общих чертах работу метода. Дана упорядоченная по возрастанию последовательность натуральных чисел. Следуя методу Эратосфена, возьмем некоторое число P изначально равное 2 – первому простому числу, и вычеркнем из последовательности все числа кратные P: 2P, 3P, 4P, …, iP (iP≤N). Далее, из получившегося списка в качестве P берется следующее за двойкой число – тройка, вычеркиваются все кратные ей числа (6, 9, 12, …). По такому принципу алгоритм продолжает выполняться для оставшейся части последовательности, отсеивая все составные числа в заданном диапазоне.

 

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

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

 

В приведенной таблице записаны натуральные числа от 2 до 100. Красным помечены те, которые удаляются в процессе выполнения алгоритма «Решето Эратосфена».

Программная реализация алгоритма Эратосфена потребует:

  1. организовать логический массив и присвоить его элементам из диапазона от 2 до N логическую единицу;
  2. в свободную переменную P записать число 2, являющееся первым простым числом;
  3. исключить из массива все числа кратные P2, ступая с шагом по P;
  4. записать в P следующее за ним не зачеркнутое число;
  5. повторять действия, описанные в двух предыдущих пунктах, пока это возможно.

Обратите внимание: на третьем шаге мы исключаем числа, начиная сразу с P2, это связано с тем, что все составные числа меньшие P будут уже зачеркнуты. Поэтому процесс фильтрации следует остановить, когда P2 станет превышать N. Это важное замечание позволяет улучшить алгоритм, уменьшив число выполняемых операций.

Так будет выглядеть псевдокод алгоритма:

 

P2
пока P2N выполнять
{
i←P2
если B[P]=true то
пока iN выполнять
{
B[i]false
ii+P
}
PP+1
}

 

Он состоит из двух циклов: внешнего и внутреннего. Внешний цикл выполняется до тех пор, пока P2 не превысит N. Само же P изменяется с шагом P+1. Внутренний цикл выполняется лишь в том случае, если на очередном шаге внешнего цикла окажется, что элемент с индексом P не зачеркнут. Именно во внутреннем цикле происходит отсеивание всех составных чисел.

Код программы на 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
33
34
#include "stdafx.h"
#include <iostream>
using namespace std;
//решето Эратосфена
void Eratosthenes(bool B[], int N)
{
int i, P;
for (P=2; P<=N; P++) B[P]=true;
P=2;
while (P*P<=N)
{
i=P*P;
if (B[P])
while (i<=N)
{
B[i]=false;
i=i+P;
}
P=P+1;
}
cout<<"Простые числа: ";
for (P=2; P<=N; P++)
if (B[P]==true) cout<<" "<<P;
}
//главная функция
void main()
{
setlocale(LC_ALL,"Rus");
int N;
cout<<"N > "; cin>>N;
bool *B=new bool[N];
Eratosthenes(B, N);
system("pause>>void");
}

 

Код программы на Pascal:

 

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
program EratosthenesAlg;
uses crt;
type Arr=array[1..1000] of boolean;
var
N, i, P: integer;
B: Arr;
{решето Эратосфена}
procedure Eratosthenes(B: Arr; N: integer);
begin
for P:=2 to N do B[P]:=true;
P:=2;
while (P*P<=N) do
begin
i:=P*P;
if B[P] then
while i<=N do
begin
B[i]:=false;
i:=i+P;
end;
P:=P+1;
end;
write('Простые числа: ');
for P:=2 to n do
if B[P]=true then write(P, ' ');
end;
{основной блок программы}
begin
clrscr;
write('N > '); read(N);
Eratosthenes(B, N);
end.

 

Решето Эратосфена для выявления всех простых чисел в заданной последовательности ограниченной некоторым N потребует O(Nlog (log N)) операций. Поэтому уместнее использовать данный метод чем, например, наиболее тривиальный и затратный перебор делителей.

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

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

Вы можете использовать эти теги HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Проверка на человечность *