Циклопедия скорбит по жертвам террористического акта в Крокус-Сити (Красногорск, МО)

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

Материал из Циклопедии
(перенаправлено с «Получение простых чисел»)
Перейти к навигации Перейти к поиску
Решето Эратосфена // Merera Ru [3:49]
Решето Эратосфена // edyo.ru [4:12]
Решето Эратосфена. Способ получения простых чисел, не превосходящих заданное число N // Элементарная Математика [15:55]

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

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

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

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

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

Nn = {1; 2; …; n} — множество натуральных чисел, не превосходящих n.

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

Алгоритм 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. j = i².
  2. Если j ≤ n, то bj = 0, j = j + i, идти к 3.
  3. i = i + 2.
  4. Если i² ≤ n, то идти к 2.
  5. k = 1, p1 = 2, i = 3.
  6. Если bi = 1, то k = k + 1, pk = i.
  7. i = i + 2.
  8. Если i ≤ n, то идти к 7.

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

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