Простые числа: Решето Эратосфена на C#

Решето Эратосфена - это древний алгоритм, который можно использовать для поиска рядов простых чисел. Это ручной алгоритм, требующий сетки чисел, которые могут быть выделены при нахождении простых чисел и вычеркнуты, когда они не являются простыми.

Простые числа

Простое число - это натуральное число, которое можно разделить только на два целых числа без остатка. Два делителя всегда равны единице, а само простое число - единице. Число один больше не считается простым числом, так как оно имеет только один целочисленный делитель. Первые пять простых чисел - 2, 3, 5, 7 и 11.

Простые числа имеют много практических применений в математике и защите данных. Однако генерирование простых чисел, особенно больших, - непростая задача. Одним из простейших алгоритмов создания списка простых чисел является Решето Эратосфена.

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

Алгоритм Решета Эратосфена использует повторяющийся ручной процесс для определения ряда простых чисел. Алгоритм требует, чтобы все числа от двух до самого высокого значения, подлежащего проверке, были записаны. Затем следует рекурсивный процесс. Во-первых, обведено первое число, не удаленное из списка или уже выделенное. Это простое число. Во-вторых, все оставшиеся числа, которые можно разделить на новое простое число, удаляются из списка. Это повторяется до тех пор, пока список не будет содержать только выделенные элементы. Затем процесс завершается, и все выделенные числа, как известно, являются простыми числами.

Адаптация алгоритма

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

Программа генератора простых чисел будет представлять собой простое консольное приложение, разработанное на C#. Для начала создайте новое консольное приложение под названием "Eratosthenes ".

Хранение простых чисел

По мере выполнения программы простые числа будут выводиться на консоль и храниться в коллекции. Для простоты мы будем использовать простой общий список, содержащий 64-разрядные целые числа. Чтобы создать этот список, добавьте следующее объявление переменной в области классов. ПРИМЕЧАНИЕ: Если вы хотите разработать эту программу с использованием .NET 1.1, используйте список массивов для коллекции.

private static List<long> _primes = new List<long>(); 

Добавление первого простого числа

Первое простое число по определению равно двум. Это также единственное четное простое число; все остальные простые числа нечетны. Чтобы воспользоваться этим преимуществом, когда идет процесс генерации простых чисел, мы будем проверять только нечетные числа. Это означает, что программа упростится, если мы добавим число два вручную при запуске программы. для этого добавьте следующие строки кода в метод Main:

_primes.Add(2);
Console.Write(2);

Создание основного цикла

В алгоритме решета, когда идентифицируется каждое простое число, все остальные числа, имеющие его в качестве множителя, удаляются из списка. Вместо того, чтобы создавать очень большой список чисел и удалять их, поскольку их делители определены как простые, мы изменим процесс. Мы пройдемся по всем нечетным числам и в каждом случае проверим, является ли значение простым, используя коллекцию ранее найденных простых чисел в качестве потенциальных делителей.

Поскольку мы уже устранили необходимость проверять число два, тестирование может начинаться с числа три и каждый раз увеличиваться на два, чтобы учитывались только нечетные числа. Поэтому мы можем создать цикл for для основной части программы, который зацикливается от 3 до самого большого доступного длинного целого числа. Чтобы создать основной цикл, добавьте в основной метод следующее:

for (long checkValue = 3; checkValue <= long.MaxValue; checkValue += 2)
{
    if (IsPrime(checkValue))
    {
        _primes.Add(checkValue);
        Console.Write("\t{0}", checkValue);
    }
}

Этот цикл использует еще не определенный метод с именем "isPrime", чтобы проверить, является ли значение простым. Если это так, то новое простое число выводится на консоль и добавляется в список простых чисел.

Метод isPrime

Заключительная задача - создать метод, который проверяет, является ли число простым. Этот метод должен возвращать логическое значение, которое является истинным, если число простое, и ложным, если это не так. Метод показан ниже:

private static bool IsPrime(long checkValue)
{
    bool isPrime = true;
 
    foreach (long prime in _primes)
    {
        if ((checkValue % prime) == 0 && prime <= Math.Sqrt(checkValue))
        {
            isPrime = false;
            break;
        }
    }
 
    return isPrime;
}

Последующий процесс довольно прост. Во-первых, предполагается, что число, переданное в параметре, является простым. Если позже будет установлено, что это не так, значение переменной "isPrime" будет изменено до того, как оно будет возвращено вызывающему методу. Затем все уже идентифицированные простые числа перебираются по порядку с помощью цикла foreach. Если какое-либо из простых чисел является делителем тестируемого значения, переменная "isPrime" изменяется и цикл останавливается. Если ни одно из простых чисел не является делителем, число должно быть простым, и метод возвращает значение true. Это эквивалентно обводке числа в процессе отсеивания.

Одна дополнительная оптимизация включена в оператор if внутри цикла. Второе условие проверяет, является ли текущее простое число меньше или равно квадратному корню из проверяемого значения. Если простое число больше квадратного корня из тестового значения, то дальнейшая проверка не требуется, так как если бы тестовое значение не было простым, парный делитель уже был бы обнаружен.

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