На днях понадобилось найти код генерации случайного простого числа. Как ни странно, в сети на этот счет полностью готового решения не нашёл. Максимум, народ выкладывал оптимизированную проверку на простоту числа.
Пришлось написать небольшой класс для генерации. Всё что делает – генерирует случайное число и сдвигает его в большую сторону до ближайшего простого. Работает, относительно, шустро, генерирует 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, которое моментально выводит число.
Использование:
Да, нечто подобное пробовал. Главная проблема тут даже не в долгой генерации, а в том, что не уверен, что итоговое число вышло простым. По крайней мере, сайты для онлайн проверки простых чисел мои числа не признавали. Грешу на Math.Sqrt(), она для double и не гарантирует точности при больших числах. Возможно, если написать свой метод извлечения корня, то можно это ограничение обойти.