Напомним, что простое число — натуральное (целое положительное) число, имеющее ровно два различных натуральных делителя — единицу и самого себя: 2, 3, 5, 7, 11, 13, … .
Зачем нужны простые числа? Первая причина имеет теоретическое значение. Наличие большого списка простых чисел позволяет проверять теоремы, которые еще не доказаны. Вторая, более практическая причина, связана с шифрованием. Электронная почта, мобильная связь, банковские операции и кредитные карты – все это защищено секретными кодами, основанными на свойствах простых чисел.
Рассмотрим постановку задачи, алгоритм решения и программную реализацию, а также анализ результатов.
Постановка задачи
Требуется сгенерировать массив простых чисел, находящихся в диапазоне от n_min до n_max, подсчитать их количество в диапазонах [2, n_max] (всего) и [n_min, n_max] (в заданном диапазоне) и иметь возможность доступа к ним, в том числе для вывода на экран. Дополнительное требование – определение времени (с точностью до секунд), необходимого для их генерации.
Алгоритм решения
Будем сохранять простые числа в массиве целых чисел типа long (System.Int64), что дает нам возможность вычислять числа до 9·1018.
Из простых чисел только одно – четное, поэтому задав пять первых простых чисел, остальные числа, начиная с 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, 108] занял около 100 секунд. Это означает, что проблема эффективности алгоритма по критерию временных затрат является актуальной, так как в алгоритмах шифрования с открытым ключом (например, RSA) используются числа, содержащие 128, 1024 и даже 2048 цифр. Понятно, что реальные программы шифрования/дешифрования гораздо более сложны.
Следующая задача «Восемь ферзей» относится к числу комбинаторных.
NEW: Наш Чат, в котором вы можете обсудить любые вопросы, идеи, поделиться опытом или связаться с администраторами.
|
|
|
|