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

Материал из Циклопедии
Перейти к: навигация, поиск
Решето Эратосфена // Merera Ru [3:49]
Решето Эратосфена // edyo.ru [4:12]
Лекция 44: Решето Эратосфена // НОУ ИНТУИТ [24:42]

Решето Эратосфена — алгоритм получения всех простых чисел на промежутке от 2 до заданного n. Заключается в том, что последовательно вычеркиваются составные числа, делящиеся на 2, 3, …, p, где p — максимальное простое число, меньшее или равное [math]\sqrt n[/math]. После вычеркивания остаются все простые числа, не превышающие n. Алгоритм назван в честь древнегреческого математика Эратосфена, который его и изобрел.

Содержание

[править] Обозначения

Введём обозначения:

n — натуральное число, n > 2;

k — количество простых чисел, не превышающих n;

pi — i-ое простое число.

[править] Алгоритмы получения простых чисел

[править] Алгоритм 1

Входные данные: n.

  1. bj = 1 ∀j ∈ Nn, i = 2, k = 0.
  2. Если bi = 0, то идти к 6.
  3. j = i².
  4. Если j ≤ n, то bj = 0, j = j + i, идти к 4.
  5. k = k + 1, pk = i.
  6. i = i + 1.
  7. Если i² ≤ n, то идти к 2.
  8. Если bi = 1, то k = k + 1, pk = i.
  9. i = i + 1.
  10. Если i² ≤ n, то идти к 8.

Выходные данные: k; {p1, p2, …, pk}.

[править] Алгоритм 2

Входные данные: n.

  1. [math]b_j=\begin{cases} 0, \ j=1 \text{ или } j \text{ — четное } \forall j \in N_n / \{2\} \\ 1, \ j=2 \text{ или } j \text{ — нечетное } \forall j \in N_n / \{1\} \\ \end{cases}, \ i=3[/math]
  2. j = i².
  3. Если j ≤ n, то bj = 0, j = j + i, идти к 3.
  4. i = i + 2.
  5. Если i² ≤ n, то идти к 2.
  6. k = 1, p1 = 2, i = 3.
  7. Если bi = 1, то k = k + 1, pk = i.
  8. i = i + 2.
  9. Если i ≤ n, то идти к 7.

Выходные данные: k; {p1,p2,…,pk}.

[править] Другие алгоритмы

Персональные инструменты
Пространства имён

Варианты
Действия
Навигация
Инструменты