На днях понадобилось найти код генерации случайного простого числа. Как ни странно, в сети на этот счет полностью готового решения не нашёл. Максимум, народ выкладывал оптимизированную проверку на простоту числа.
Пришлось написать небольшой класс для генерации. Всё что делает – генерирует случайное число и сдвигает его в большую сторону до ближайшего простого. Работает, относительно, шустро, генерирует UInt32, но это не принципиально. Самой затратной операцией оказалось, как ни странно, деление с остатком. 🙂
public class PrimeNumberGenerator
{
private readonly Random _random = new Random();
public uint Generate()
{
var numberBytes = new byte[4];
_random.NextBytes(numberBytes);
uint number = BitConverter.ToUInt32(numberBytes, 0);
while (!IsPrime(number))
{
unchecked
{
number++;
}
}
return number;
}
private static bool IsPrime(uint number)
{
if ((number & 1) == 0) return (number == 2);
var limit = (uint)Math.Sqrt(number);
for (uint i = 3; i <= limit; i += 2)
{
if ((number % i) == 0) return false;
}
return true;
}
}
Использование:
var generator = new PrimeNumberGenerator(); uint prime = generator.Generate();
Отлично! Большое спасибо! Работает быстро и без багов.
Рад, что пригодилось:)
Отлично работает,быстро и точно, но хотелось бы увидеть версию с генерацией UInt64.
К сожалению, для UInt64 данный метод не подойдет – слишком долгий перебор, да и не факт, что Math.Sqrt для такого большого числа будет правильно вычислять корень. Нужно искать кардинально иное решение.
В принципе вот переделанный класс под UInt64, но число генерируется около минуты, в отличии от приведенного UInt32, которое моментально выводит число.
public class PrimeNumberGenerator_x64 { private Random _random64 = new Random(); Stopwatch stopWatch = new Stopwatch(); public ulong Generate_64() { stopWatch.Start(); var p_numberBytes = new byte[8]; _random64.NextBytes(p_numberBytes); ulong p_number64 = BitConverter.ToUInt64(p_numberBytes, 0); while (!IsPrime_64(p_number64)) { unchecked { p_number64++; } } stopWatch.Stop(); TimeSpan ts = stopWatch.Elapsed; string elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:00}", ts.Hours, ts.Minutes, ts.Seconds, ts.Milliseconds / 10); MessageBox.Show("RunTime: " + elapsedTime, "Prime Number Generator"); return p_number64; } private static bool IsPrime_64(ulong p_number64) { if ((p_number64 & 1) == 0) return (p_number64 == 2); var limit = (ulong)Math.Sqrt(p_number64); for (ulong i = 3; i <= limit; i += 2) { if ((p_number64 % i) == 0) return false; } return true; } }Использование:
Да, нечто подобное пробовал. Главная проблема тут даже не в долгой генерации, а в том, что не уверен, что итоговое число вышло простым. По крайней мере, сайты для онлайн проверки простых чисел мои числа не признавали. Грешу на Math.Sqrt(), она для double и не гарантирует точности при больших числах. Возможно, если написать свой метод извлечения корня, то можно это ограничение обойти.