Задача «Простые числа»

Напомним, что простое число — натуральное (целое положительное) число, имеющее ровно два различных натуральных делителя — единицу и самого себя: 2, 3, 5, 7, 11, 13, … .

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

Рассмотрим постановку задачи, алгоритм решения и программную реализацию, а также анализ результатов.

Постановка задачи

Требуется сгенерировать массив простых чисел, находящихся в диапазоне  от  n_min до  n_max, подсчитать их количество в диапазонах [2, n_max] (всего) и [n_min, n_max] (в заданном диапазоне) и иметь возможность доступа к ним, в том числе для вывода на экран.  Дополнительное требование – определение времени (с точностью до секунд), необходимого для их генерации.

Алгоритм решения

Будем сохранять простые числа  в массиве целых чисел типа long (System.Int64), что дает нам возможность вычислять числа до 9·10¹⁸.

Из простых чисел только одно – четное, поэтому задав пять первых простых чисел, остальные числа, начиная с 13, будем искать среди нечетных чисел.

Проверка очередного кандидата в простые числа состоит в вычислении остатка от деления его на уже имеющиеся простые числа, причем они не должны превышать z — квадратного корня из исследуемого числа.

Примечание. Такое полезное ограничение цикла связано с тем, что если число  х не является простым, то оно может быть представлено произведением как минимум двух простых чисел: x=z1*z2, одно из которых, например,  z1<=z. Следовательно, в проверке деления нацело на число z2>z нет необходимости.

Программная реализация

Начнем проект с нуля, придумаем имя классу, например, ProstyeChisla.

Член-данные класса:
 public long[] prost = new long[10000000]; // массив простых чисел
 public long n_min; // нижняя граница диапазона
 public long n_max; // верхняя граница диапазона
 public DateTime tstart, tfinish; // время старта и финиша поиска

Методы класса:
public long poisk()  // поиск
bool yes_pr(long x) // проверка, является ли х простым
public void TimePoisk() // интервал времени генерации

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

В методе Main() класса Program инициализируется объект pch класса ProstyeChisla. Задаются границы диапазона чисел  [pch.n_min, pch.n_max] (поля объекта pch).

Вызывается метод pch.poisk(), генерирующий в массив простые числа в диапазоне [2,  n_max], и возвращающий общее число простых чисел  k. В этом методе запоминаются временные метки  tstart и tfinish — время старта и финиша поиска, которые после завершения поиска в методе TimePoisk() используются для вычисления времени поиска.

Для вывода массива простых чисел в диапазоне [n_min, n_max]  используем цикл  for с проверкой условия  pch.prost[i] > pch.n_min, внутри которого производим подсчет чисел в заданном диапазоне (переменная j).

В завершение выведем числа k и j.

Остальное должно быть понятно из текста программы:

using System;
namespace ПростыеЧисла
{
    class ProstyeChisla
    {
        // массив простых чисел
        public long[] prost = new long[10000000];
        public long n_min; // нижняя граница
        public long n_max; // верхняя граница
        // время старта и финиша поиска
        public DateTime tstart, tfinish;
        // поиск простых чисел 
        public long poisk()
        {
            tstart = DateTime.Now;
            prost[0] = 2;
            prost[1] = 3;
            prost[2] = 5;
            prost[3] = 7;
            prost[4] = 11;
            long x = 13;
            long k = 5;
            while (x <= n_max)
            {
                if (yes_pr(x))
                {
                    prost[k] = x;
                    k++;
                }
                x = x + 2;
            }
            tfinish = DateTime.Now;
            return k;
        }
        // является ли очередное число x простым?
        bool yes_pr(long x)
        {
            bool b = true;
            double y = Math.Sqrt(x);
            long z = Convert.ToInt64(y + 0.5);
            long k = 1;
            while (prost[k] < z)
            {
                if (x % prost[k] == 0)
                {
                    b = false;
                    break;
                }
                k++;
            }
            return b;
        }
        public void TimePoisk()
        {
            int dt, ds, dm, dh;
            dt = tfinish.Hour * 3600 + tfinish.Minute * 60 + tfinish.Second - tstart.Hour * 3600 - tstart.Minute * 60 - tstart.Second;
            dh = dt / 3600;
            dm = (dt - dh * 3600) / 60;
            ds = (dt - dh * 3600 - dm * 60);
            if (dt < 60)
                Console.WriteLine("Время поиска: секунд - {0}", ds);
            else if (dt < 3600)
                Console.WriteLine("Время поиска: минут - {0}, секунд - {1}", dm, ds);
            else
                Console.WriteLine("Время поиска: часов - {0}, минут - {1}, секунд - {2}", dh, dm, ds);
        }
    }
    // начальный класс
    class Program
    {
        static void Main(string[] args)
      {
         ProstyeChisla pch = new ProstyeChisla();
         Console.Write("Введите нижнюю границу простых чисел: ");
         pch.n_min = Convert.ToInt64(Console.ReadLine());
         Console.Write("Введите верхнюю границу простых чисел: ");
         pch.n_max = Convert.ToInt64(Console.ReadLine());
         long k = pch.poisk();
         pch.TimePoisk();
         long j = 0;
         for (int i = 0; i < k; i++)
             if (pch.prost[i] > pch.n_min)
             {
                 Console.Write(pch.prost[i].ToString() + "\t");
                 j++;
             }
         Console.WriteLine("\nВсего: {0}, в диапазоне: {1}", k, j);
         Console.ReadKey();
      }
   }
}

Результат

Заметка об эффективности алгоритма

Обратите внимание, что поиск 5,76 млн простых чисел в диапазоне [2, 10⁸] занял около 100 секунд. Это означает, что проблема эффективности алгоритма по критерию временных затрат является актуальной, так как в  алгоритмах шифрования с открытым ключом (например, RSA) используются числа, содержащие 128, 1024 и даже 2048 цифр. Понятно, что реальные программы шифрования/дешифрования гораздо более сложны.

Следующая задача «Восемь ферзей» относится к числу комбинаторных.