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

Решето Ератосфена – це алгоритм для пошуку всіх простих чисел від першого простого числа(2) до заданого. Цей алгоритм був розроблений давньогрецьким філософом та математиком Ератосфеном.

Опис алгоритму

Для знаходження всіх простих чисел менших за задане N, записуємо всі числа від 2 до N.

  1. Оскільки першим простим числом є 2, то видаляємо зі списку всі числа кратні двом.
  2. Наступне число, що залишилося - 3, воно також є простим. На цьому кроці видаляємо числа, що діляться на три.
  3. Беремо наступне число і видаляємо всі кратні йому.
  4. Повторюємо цикл для всіх чисел менших за N.

Розглянемо приклад роботи решета Ератосфена для чисел до 12:

2 3 4 5 6 7 8 9 10 11

Видаляємо кратні двійці:

2 3 4 5 6 7 8 9 10 11

Видаляємо кратні трійці:

2 3 4 5 6 7 8 9 10 11

Для наступних чисел в списку не знаходиться кратних. Всі числа, що залишилися є простими.

Реалізація алгоритму “Решето Ератосфена”

Оскільки нам потрібно видаляти елементи зі списку, а масиви не дозволяють видалення, для зберігання даних, використаємо клас List з бібліотеки System.Collections.Generic.

using System;
using System.Collections.Generic;

class Program
{
    static List<uint> SieveEratosthenes(uint n)
    {
        var numbers = new List<uint>();
        //заповнення списку числами від 2 до n-1
        for (var i = 2u; i < n; i++)
        {
            numbers.Add(i);
        }

        for (var i = 0; i < numbers.Count; i++)
        {
            for (var j = 2u; j < n; j++)
            {
                //видаляємо кратні числа зі списку
                numbers.Remove(numbers[i] * j);
            }
        }

        return numbers;
    }


    static void Main(string[] args)
    {
        Console.Write("N = ");
        var n = Convert.ToUInt32(Console.ReadLine());
        var primeNumbers = SieveEratosthenes(n);
        Console.WriteLine("Прості числа менші за {0}:", n);
        Console.WriteLine(string.Join(", ", primeNumbers));
        Console.ReadLine();
    }
}

Результат роботи програми:

Дивіться також: