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

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

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

Смотрите также: