Алгоритмы поиска простых чисел в C#

Простое число — это целое положительное число, имеющее ровно два различных натуральных делителя — единицу и самого себя. Определение того является ли число простым или нет — это одна из самых распространенных задач, решаемых в рамках курса лабораторных работ по информатике. Ниже будет представлена реализация алгоритма поиска простых чисел в C#, а также использование различных циклов для вывода простых чисел.

Задача №1

Проверить является ли число простым и вывести результат вычисления в консоль.

Алгоритм определения простого числа

Для того, чтобы проверить является ли число N простым необходимо:

1. Задаем значение N
2. Задаем цикл for от 2 до N-1 (счётчик цикла обозначим, например, как i)
   1. Если остаток от деление N на i равен нулю, то число не является простым — выходим из цикла
   2. Если остаток от деления N на i не равен нулю, то переходим к следующей итерации цикла
3. Если цикл полностью пройден, то число является простым.

Реализация алгоритма определения простого числа в C#

Метод определения простого числа в C#, реализующий представленный выше алгоритм может быть представлен следующим образом:

public bool IsPrime(int number)
{
    for (int i = 2; i < number; i++)
    {
        if (number % i == 0)
            return false;
    }
    return true;
}

Пример определения простых чисел из диапазона от 1 до N

Если по условиям задачи конечное значение диапазона задается в виде числа N, то здесь удобно использовать цикл for или while. Пример программы с использованием цикла for представлен ниже:

using System;

namespace Prime
{
    class Program
    {
        public static bool IsPrime(int number) 
        { 
            for (int i = 2; i < number; i++) 
            { 
                if (number % i == 0) 
                    return false; 
            } 
            return true; 
        }

        static void Main(string[] args)
        {
            Console.WriteLine("Введите конечное значение диапазона 1...N и нажмите Enter");
            Console.WriteLine("N = "); 
            if ((!int.TryParse(Console.ReadLine(), out int result))||(result<0))
                Console.WriteLine("Число должно быть положительным и целым");
            Console.WriteLine($"Простые числа из диапазона от 1 до {result}");
            int count = 0;
            for (int i = 1; i <= result; i++)
            {
                if (IsPrime(i))
                {
                    Console.Write($"{i} ");
                    count++;
                }
            }
            Console.WriteLine("");
            Console.WriteLine($"Найдено {count} простых чисел из диапазона от 1 до {result}");
        }
    }
}

Строго говоря, число 1 не является ни простым не составным, поэтому его можно было бы исключить из цикла, что мы и сделаем в следующем примере.

Пример определения заданного количества простых чисел

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

using System;

namespace Prime
{
    class Program
    {
        public static bool IsPrime(int number) 
        { 
            for (int i = 2; i < number; i++) 
            { 
                if (number % i == 0) 
                    return false; 
            } 
            return true; 
        }

        static void Main(string[] args)
        {
            Console.WriteLine("Введите количество простых чисел которые необходимо найти");
            Console.WriteLine("N = "); 
            if ((!int.TryParse(Console.ReadLine(), out int result))||(result<=0))
                Console.WriteLine("Число должно быть положительным и целым");
            Console.WriteLine($"Первые {result} простых чисел");
            int count = 0; //количество найденных простых чисел
            int number = 1; //очередное число, проверку которого необходимо найти
            int total = 0; //общее количество проверенных чисел
            while (count<result)
            {
                total++;
                number++;
                if (IsPrime(number))
                {
                    Console.Write($"{number} ");
                    count++;
                }
            }
            Console.WriteLine("");
            Console.WriteLine($"Найдено {count} простых чисел. Проверено {total} чисел");
        }
    }
}

Результатом работы программы будет вывод в консоль первых N простых чисел.

Итого

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