Генерация случайного простого числа

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

Пришлось написать небольшой класс для генерации. Всё что делает – генерирует случайное число и сдвигает его в большую сторону до ближайшего простого. Работает, относительно, шустро, генерирует 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();

Генерация случайного простого числа: 6 комментариев

  1. Никита

    Отлично работает,быстро и точно, но хотелось бы увидеть версию с генерацией UInt64.

    1. Андрей Михайлов Автор записи

      К сожалению, для UInt64 данный метод не подойдет – слишком долгий перебор, да и не факт, что Math.Sqrt для такого большого числа будет правильно вычислять корень. Нужно искать кардинально иное решение.

      1. Никита

        В принципе вот переделанный класс под 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;
                }
            }
        

        Использование:

        var generator = new PrimeNumberGenerator();
        uint prime = generator.Generate();
        
        1. Андрей Михайлов Автор записи

          Да, нечто подобное пробовал. Главная проблема тут даже не в долгой генерации, а в том, что не уверен, что итоговое число вышло простым. По крайней мере, сайты для онлайн проверки простых чисел мои числа не признавали. Грешу на Math.Sqrt(), она для double и не гарантирует точности при больших числах. Возможно, если написать свой метод извлечения корня, то можно это ограничение обойти.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *