Как в информатике найти простое число

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

«Самое большое простое число 2^32582657-1. И я с гордостью утверждаю, что запомнил все его цифры… в двоичной форме».
Карл Померанс

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

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

Решето Эратосфена — алгоритм, предложенный древнегреческим математиком Эратосфеном. Этот метод позволяет найти все простые числа меньше заданного числа n. Суть метода заключается в следующем. Возьмем набор чисел от 2 до n. Вычеркнем из набора (отсеим) все числа делящиеся на 2, кроме 2. Перейдем к следующему «не отсеянному» числу — 3, снова вычеркиваем все что делится на 3. Переходим к следующему оставшемуся числу — 5 и так далее до тех пор пока мы не дойдем до n. После выполнения вышеописанных действий, в изначальном списке останутся только простые числа.

Алгоритм можно несколько оптимизировать. Так как один из делителей составного числа n обязательно

, алгоритм можно останавливать, после вычеркивания чисел делящихся на

.

Иллюстрация работы алгоритма из Википедии:

Сложность алгоритма составляет

, при этом, для хранения информации о том, какие числа были вычеркнуты требуется

памяти.

Существует ряд оптимизаций, позволяющих снизить эти показатели. Прием под названием wheel factorization состоит в том, чтобы включать в изначальный список только числа взаимно простые с несколькими первыми простыми числами (например меньше 30). В теории предлагается брать первые простые примерно до

. Это позволяет снизить сложность алгоритма в

раз. Помимо этого для уменьшения потребляемой памяти используется так называемое сегментирование. Изначальный набор чисел делится на сегменты размером

и для каждого сегмента решето Эратосфена применяется по отдельности. Потребление памяти снижается до

.

Решето Аткина

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

Свойство 1

Если n — положительное число, не кратное квадрату простого числа и такое, что

. То n — простое, тогда и только тогда, когда число корней уравнения

нечетно.

Свойство 2

Если n — положительное число, не кратное квадрату простого числа и такое, что

. То n — простое, тогда и только тогда, когда число корней уравнения

нечетно.

Свойство 3

Если n — положительное число, не кратное квадрату простого числа и такое, что

. То n — простое, тогда и только тогда, когда число корней уравнения

нечетно.

Доказательства этих свойств приводятся в этой статье.

На начальном этапе алгоритма решето Аткина представляет собой массив A размером n, заполненный нулями. Для определения простых чисел перебираются все

. Для каждой такой пары вычисляется

,

,

и значение элементов массива

,

,

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

Из описания алгоритма следует, что вычислительная сложность решета Аткина и потребление памяти составляют

. При использовании wheel factorization и сегментирования оценка сложности алгоритма снижается до

, а потребление памяти до

.

Числа Мерсенна и тест Люка-Лемера

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

Один из таких методов проверки — тест Люка-Лемера. Это детерминированный и безусловный тест простоты. Это означает, что прохождение теста гарантирует простоту числа. К сожалению, тест предназначен только для чисел особого вида

, где p — натуральное число. Такие числа называются числами Мерсенна.

Тест Люка-Лемера утверждает, что число Мерсенна

простое тогда и только тогда, когда p — простое и

делит нацело

-й член последовательности

задаваемой рекуррентно:

для

.

Для числа

длиной p бит вычислительная сложность алгоритма составляет

.

Благодаря простоте и детерминированности теста, самые большие известные простые числа — числа Мерсенна. Самое большое известное простое число на сегодня —

, его десятичная запись состоит из 24,862,048 цифр. Полюбоваться на эту красоту можно здесь.

Теорема Ферма и тест Миллера-Рабина

Простых чисел Мерсенна известно не очень много, поэтому для криптографии с открытым ключом необходим другой способ поиска простых чисел. Одним из таким способов является тест простоты Ферма. Он основан на малой теореме Ферма, которая гласит, что если n — простое число, то для любого a, которое не делится на n, выполняется равенство

. Доказательство теоремы можно найти на Википедии.

Тест простоты Ферма — вероятностный тест, который заключается в переборе нескольких значений a, если хотя бы для одного из них выполняется неравенство

, то число n — составное. В противном случае, n — вероятно простое. Чем больше значений a использовано в тесте, тем выше вероятность того, что n — простое.

К сожалению, существуют такие составные числа n, для которых сравнение

выполняется для всех a взаимно простых с n. Такие числа называются числам Кармайкла. Составные числа, которые успешно проходят тест Ферма, называются псевдопростыми Ферма. Количество псевдопростых Ферма бесконечно, поэтому тест Ферма — не самый надежный способ определения простых чисел.

Тест Миллера-Рабина

Более надежных результатов можно добиться комбинируя малую теорему Ферма и тот факт, что для простого числа p не существует других корней уравнения

, кроме 1 и -1. Тест Миллера-Рабина перебирает несколько значений a и проверяет выполнение следующих условий.

Пусть p — простое число и

, тогда для любого a справедливо хотя бы одно из условий:

1. 
2. Существует целое число r < s такое, что

По теореме Ферма

, а так как

из свойства о корнях уравнения

следует что если мы найдем такое a, для которого одно из условий не выполняется, значит p — составное число. Если одно из условий выполняется, число a называют свидетелем простоты числа n по Миллеру, а само число n — вероятно простым.

Чем больше свидетелей простоты найдено, тем выше вероятность того, что n — простое. Согласно теореме Рабина вероятность того, что случайно выбранное число a окажется свидетелем простоты составного числа составляет приблизительно

.

Следовательно, если проверить k случайных чисел a, то вероятность принять составное число за простое

.

Сложность работы алгоритма

, где k — количество проверок.

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

Он смог сгенерировать такие составные числа, которые успершно прошли тест на простоту в библиотеках OpenSSL, CryptLib, JavaScript Big Number и многих других.

Тест Люка и Тест Baillie–PSW

Чтобы избежать уязвимости, связанные с ситуациями, когда сгенерированное злоумышленником составное число, выдается за простое, Мартин Альбрехт предлагает использовать тест Baillie–PSW. Несмотря на то, что тест Baillie–PSW является вероятностным, на сегодняшний день не найдено ни одно составное число, которое успешно проходит этот тест. За нахождение подобного числа в 1980 году авторы алгоритма пообещали вознаграждение в размере $30. Приз пока так и не был востребован.

Ряд исследователей проверили все числа до

и не обнаружили ни одного составного числа, прошедшего тест Baillie–PSW. Поэтому, для чисел меньше

тест считается детерминированным.

Суть теста сводится к последовательной проверке числа на простоу двумя различными методами. Один из этих методов уже описанный выше тест Миллера-Рабина. Второй — тест Люка на сильную псевдопростоту.

Тест Люка на сильную псевдопростоту

Последовательности Люка — пары рекуррентных последовательностей

, описываемые выражениями:

Пусть

и

— последовательности Люка, где целые числа P и Q удовлетворяют условию

Вычислим символ Якоби:

.

Найдем такие r, s для которых выполняется равенство

Для простого числа n выполняется одно из следующих условий:

1. n делит
2. n делит для некоторого j < r

В противном случае n — составное.

Вероятность того, что составное число n успешно пройдет тест Люка для заданной пары параметров P, Q не превышает 4/15. Следовательно, после применения теста k раз, эта вероятность составляет

.

Тесты Миллера-Рабина и Люка производят не пересекающиеся множества псевдопростых чисел, соответственно если число p прошло оба теста, оно простое. Именно на этом свойстве основывается тест Baillie–PSW.

Заключение

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

. Затем для каждого числа p из списка, с помощью теста Люка-Лемера, на простоту проверяется

.

Чтобы сгенерировать большое простое число в криптографических целях, выбирается случайное число a и проверяется тестом Миллера-Рабина или более надежным Baillie–PSW. Согласно теореме о распределении простых чисел, у случайно выбранного числа от 1 до n шанс оказаться простым примерно равен

. Следовательно, чтобы найти простое число размером 1024 бита, достаточно перебрать около тысячи вариантов.

P.S. Исходники

Реализацию всех описанных алгоритмов на Go можно посмотреть на GitHub.

Простые числа – это натуральные числа, большие единицы, которые имеют только два делителя: единицу и само это число.

Примеры простых чисел: 2 , 3, 5, 7, 11, 13…

(Единица не является простым числом!)

Существует множество задач, связанных с простыми числами, и хотя формулируются они достаточно просто, решить их бывает очень трудно. Некоторые свойства простых чисел еще не открыты. Это побудило немецкого математика Германа Вейля (Wayl, 1885-1955) так охарактеризовать простые числа: «Простые числа – это такие существа, которые всегда склонны прятаться от исследователя».

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

Не будем гнаться за рекордами, а рассмотрим несколько алгоритмов нахождения простых чисел.

Задача 1. Определение простого числа.

Составить программу, которая будет проверять, является ли введенное число простым.

Самый простой путь решения этой задачи – проверить, имеет ли данное число n (n >= 2) делители в интервале [2; n-1]. Если делители есть, число n – составное, если – нет, то – простое. При реализации алгоритма разумно делать проверку на четность введенного числа, поскольку все четные числа делятся на 2 и являются составными числами, то, очевидно, что нет необходимости искать делители для этих чисел. Логическая переменная flag в программе выступает в роли “флаговой” переменной и повышает наглядность программы, так, если flag = true, то n –простое число; если у числа n есть делители, то “флаг выключаем” с помощью оператора присваивания flag:= false, таким образом, если flag = false, то n – составное число.

  var  
  n,i: longint;
  flag: boolean;
  begin  writeln('vvod n');
  read(n);  
  if n = 2 then flag := true
         else if not odd (n) then flag :=  false           
         else  begin                 
              flag := true;                 
              for i := 2 to n-1 do                 
              if n mod i = 0 then flag  := false                 
              end;
  if flag then writeln('Yes') else writeln('No'); 
  readln;
  end.

Задача 2. Нахождение простых чисел в заданном интервале.

Составить программу, которая напечатает все простые числа в заданном интервале [2, m], для m>3 и подсчитает их количество.

Для реализации данного алгоритма необходимо проверить каждое число, находящееся в данном интервале, — простое оно или нет. Однако для этого машине пришлось бы потратить много времени. Поэтому подумаем, каким образом можно оптимизировать алгоритм, описанный в задаче 1, применительно к задаче 2?

Будем использовать следующие приемы оптимизации алгоритма:

1. рассматривать только нечетные числа;
2. использовать свойство: наименьшее число, на которое делится натуральное число n, не превышает целой части квадратного корня из числа n;
3. прерывать работу цикла, реализующего поиск делителей числа, при нахождении первого же делителя с помощью процедуры Break, которая реализует немедленный выход из цикла и передает управление оператору, стоящему сразу за оператором цикла.

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

Счетчик чисел будет находиться в переменной k. Когда очередное простое число найдено, он увеличивается на 1. Простые числа выводятся по 10 в строке, как только значение счетчика становится кратным 10, курсор переводится на новую строку.

 var
 m,n,i,k: longint;
 flag: boolean;
 begin
 writeln('vvod m>3');
 readln(m);
 write('      2      3');
 n:=3; k := 2;  n := n+2;
 while n <= m do begin
 flag := true;
 for i := 2 to round(sqrt(n)) do
   if n mod i = 0 then begin flag :=  false;
                    break
                end;
   if flag then begin
                write(n:7);
                k := k+1;
                if k mod 10 = 0 then writeln
                end;
 n := n+2
 end;
 writeln;
 writeln('kol-vo = ',k);
 readln
 end.

Близнецы

Два нечетных простых числа, разнящихся на два, называются близнецами. Близнецами являются, например, числа 5 и 7, 11 и 13, 17 и 19 и т.д. В начале натурального ряда такие пары чисел встречаются достаточно часто, но, по мере того как мы продвигаемся в область больших чисел, их становится все меньше и меньше. Известно, что в первой сотне имеется целых 8 близнецов, дальше они расположены очень неравномерно, их можно обнаружить все реже и реже, гораздо реже, нежели сами простые числа. До сих пор неясно, конечно ли число близнецов. Более того, еще не найден способ, посредством которого можно было бы разрешить эту проблему.

Задача 3. Поиск пар чисел близнецов.

Написать программу, которая будет находить все числа близнецы в интервале [2; 1000] и подсчитывать количество пар чисел близнецов.

Фактически будем использовать алгоритм и программу Задачи 2. В этом алгоритме нужно использовать дополнительные переменные для хранения двух “последних” простых чисел и проверять условие наличия близнецов – их разность должна быть равна двум.

 var
 m,n,n1,n2,i,k: longint;
 flag: boolean;
 begin
 m :=1000;
 n1 := 2; n2 := 3; n := n2+2; k:=0;
 while n <= m do begin
 flag := true;
 for i := 2 to round(sqrt(n)) do
   if n mod i = 0 then begin flag := false;
                    break
                end;
   if flag then begin  n1 := n2; n2 := n;
                 if (n2 -n1) = 2 then  begin
                               k := k+1;
                               write(n1:4,n2:4,' ');
                               if k mod 5 = 0 then writeln
                               end
             end;
 n := n+2
 end;
 writeln;
 writeln('kol -vo par =',k);
 readln
 end.

Задача 4. Нахождение простых чисел в заданном интервале с выводом в выходной файл.

Реализовать алгоритм задачи 2 с выводом простых чисел в выходной файл по 10 в строке. Последняя строка файла должна содержать информацию о количестве простых чисел в заданном интервале.

 var
 m,n,i,k: longint;
 flag: boolean;
 f:text;
 begin
 assign(f,'output.txt'); rewrite(f);
 writeln('vvod m > 3');
 readln(m);
 write(f,'  2  3');
 n:=3; k := 2;  n := n+2;
 while n <= m do begin
 flag := true;
 for i := 2 to round(sqrt(n)) do
   if n mod i = 0 then begin flag := false;
                    break
                end;
   if flag then begin
            write(f,n:7);
            k := k+1;
            if k mod 10 = 0 then  writeln(f)
            end;
 n := n+2
 end;
 writeln(f);
 writeln(f,'kol-vo = ',k);
 close(f)
 end.

Задача 5. Приемы оптимизации алгоритма задачи 4.

Оптимизировать алгоритм задачи 4 следующим образом: найденные простые числа записывать в файл, делимость очередного кандидата проверять только на числа из этого файла.

Словесное описание алгоритма:

1. Вводим правую границу диапазона – m;
2. Записываем двойку и тройку в файл;
3. Пока очередное нечетное число i <= m :
   1. проверять очередное нечетное число на наличие делителей из данного файла;
   2. если есть делители, рассматривать очередное нечетное число, если нет — производить дозапись в “хвост” файла.
4. По окончании просмотра диапазона ( i > m ), вывести в файл количество простых чисел.

{Простые  до m}
   label n1;
   var 
   m,i,j,k,q : longint;
   f : text;
   begin
      assign(f,'output.txt');
      rewrite(f);
      Writeln('vvod  m');  {m – правая граница диапазона чисел}
      readln(m);
      k := 0;             {k – счетчик количества  простых чисел}
      if  m >= 2 then begin
                   write(f,'  ':6,'2',' ':6);
                   k:=k+1
                 end;
      if m >= 3 then begin
                  write(f,'3');
                  k:=k+1
                end;
      close(f);
      i:=5;                {В i находится текущее  нечетное число}
      while  i <= m do
       begin  
        reset(f);
         {проверка делимости i на простые числа  q из файла}
         for j:=1  to k do
           begin
            read(f,q);
            if (q*q>i) then break;
            if (i mod q=0) then goto n1
           end;
        close(f); 
             {дозапись в ‘хвост’ файла простых  чисел}
        append(f);
            k:=k+1;
            Write (f,i:7);
            if k mod 10 = 0 then  writeln(f);
            close(f);
        {следующее нечетное число I  <= m}
        n1: i:=i+2
        end;
       {дозапись в конец файла количества простых  чисел} 
        append(f);
   writeln(f);
   writeln(f,'     kol -vo = ',k);
   close(f)
   end.

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

Греческий математик Эратосфен (275-194 гг. до н.э.) предложил интересный метод нахождения простых чисел в интервале [2; n]. Он написал на папирусе, натянутом на рамку, все числа от 2 до 10000 и прокалывал составные числа. Папирус стал, как решето, которое “просеивает” составные числа, а простые оставляет. Поэтому такой метод называется Эратосфеновым решетом. Рассмотрим подробнее этот метод. 

Пусть написаны числа от 2 до n:

2 3 4 5 6 7 8 9 10 11 12 . . .

Первое неперечеркнутое число в строке является простым. Таким образом, 2 – простое число. Начинаем “просеивание” с него, перечеркивая все числа, которые делятся на 2:

2 3 4 5 6 7 8 9 10 11 12 . . .

Далее берем следующее по порядку неперечеркнутое число и перечеркиваем все числа, кратные ему и т. д. Таким образом, мы перечеркнем все составные числа, а простые останутся неперечеркнутыми:

2 3 4 5 6 7 8 9 10 11 12 . . .

Все числа указанного интервала можно рассматривать как множество и в дальнейшем из этого множества будем исключать (отсеивать) все составные числа.

Задача 6. Нахождение простых чисел с помощью решета Эратосфена.

Реализовать алгоритм решета Эратосфена с помощью организации работы с множествами.

Словесное описание алгоритма:

1. Выделим из первых n натуральных чисел все простые числа (решето Эратосфена).
2. Вначале формируем множество BeginSet, состоящее из всех целых чисел в диапазоне от 2 до n. Множество PrimerSet будет содержать искомые простые числа.
3. Затем циклически повторим действия:
   1. взять из BeginSet первое входящее в него число next и поместить его в PrimerSet;
   2. удалить из BeginSet число next и все другие числа, кратные ему, т. е. 2* next, 3* next и т. д.

Цикл повторяется до тех пор, пока множество BeginSet не станет пустым. Программу нельзя использовать для произвольного n, т. к. в любом множестве не может быть больше 256 элементов. (Для расширения интервала простых чисел можно разбить одно большое множество на несколько маленьких, т. е. представить большое множество в виде массива малых множеств. Этот случай рассматривать не будем. Можно предложить наиболее заинтересованным учащимся самостоятельно рассмотреть этот вариант.)

{Выделение всех простых чисел из первых n целых}
 const
 n = 255; {Количество элементов исходного множества}
 type
 SetOfNumber = set of 1..n;
 var
 n1, next, i: word;                    {Вспомогательные  переменные}
 BeginSet,                             {Исходное  множество}
 PrimerSet: SetOfNumber;               {Множество простых чисел}
 begin
   BeginSet := [2..n];                 {Создаем исходное множество}
   PrimerSet  :=[2];                 {Поместить в PrimerSet  первое число из BeginSet}
   next := 2;                          {Первое простое  число}
    while BeginSet  <> [] do            {Начало  основного цикла}
          begin
           n1 := next;   {n1 –число, кратное  очередному простому (next)}
            {Цикл удаления из исходного  множества непростых чисел:} 
           while n1  <= n do
  begin
  Exclude(BeginSet,n1);
  n1 := n1+next         {Следующее кратное}
  end;        {Конец цикла  удаления}
  Include(PrimerSet,next);
  {Получение следующего простого, которое  есть первое невычеркнутое
  из исходного множества}

  repeat
  Inc(next);
  until  (next in BeginSet) or (next > n)
  end;  {Конец основного цикла}
  {Вывод результатов:}

  for  i := 1 to n do
  if i in PrimerSet then write(i:5);
  readln
  end.

Литература:

1. Е.В. Андреева Методика обучения основам программирования на уроках информатики. Лекции 1-8. – М.: Педагогический университет «Первое сентября», 2006.
2. В.А. Дагене, Г.К. Григас, А.Ф. Аугутис 100 задач по программированию. – М.: Просвещение, 1993. — 255 с.
3. В.В. Фаронов Турбо Паскаль 7.0. Начальный курс. Учебное пособие. – М.: «Нолидж», 1999. — 616 с.

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

Задача №1

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

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

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

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

Метод определения простого числа в 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#. В зависимости от условий задачи, мы использовали различные виды циклов для поиска набора простых чисел.