Простые числа с использованием решета Аткина с BigInteger

Кто-нибудь знает об алгоритме C # Sieve of Atkin, использующем BigInteger? Насколько я понимаю, это самый известный из существующих в настоящее время алгоритмов разложения на простые множители.

У меня сейчас есть такая функция:

/// <summary>
        /// Finds prime numbers using the Sieve of Atkins algorithm.
        /// </summary>
        /// <param name="max">The limit of the prime list.</param>
        /// <returns>The list of prime numbers.</returns>
        public List<int> FindPrimes(int max)
        {
            var isPrime = new bool[max + 1];
            var sqrt = (int) Math.Sqrt(max);

            Parallel.For(1, sqrt, x =>
            {
                var xx = x * x;
                for (int y = 1; y <= sqrt; y++)
                {
                    var yy = y * y;
                    var n = 4 * xx + yy;
                    if (n <= max && (n % 12 == 1 || n % 12 == 5))
                        isPrime[n] ^= true;

                    n = 3 * xx + yy;
                    if (n <= max && n % 12 == 7)
                        isPrime[n] ^= true;

                    n = 3 * xx - yy;
                    if (x > y && n <= max && n % 12 == 11)
                        isPrime[n] ^= true;
                }
            });

            var primes = new List<int>() { 2, 3 };
            for (int n = 5; n <= sqrt; n++)
            {
                if (isPrime[n])
                {
                    primes.Add(n);
                    int nn = n * n;
                    for (int k = nn; k <= max; k += nn)
                        isPrime[k] = false;
                }
            }

            for (int n = sqrt + 1; n <= max; n++)
                if (isPrime[n])
                    primes.Add(n);

            return primes;

        }

Но я хотел бы иметь сигнатуру функции, которая больше похожа на приведенную ниже, чтобы она могла использовать одно число для проверки и вывода true, если число простое.

public bool IsPrime(BigInteger number) { ... }

c# math primes prime-factoring
person Adam    schedule 14.02.2015    source источник
comment
возможный дубликат Более быстрый способ проверить, является ли число премьер?   -  person rducom    schedule 15.02.2015
comment
Этот вопрос конкретно касается BigInteger. Плюс ответы на этот вопрос с помощью простого пробного деления.   -  person Adam    schedule 15.02.2015
comment
Я согласен. Я уже ломаю голову над твоей проблемой :)   -  person rducom    schedule 15.02.2015
comment
Из-за характера алгоритма, похоже, мне может потребоваться переключиться на что-то другое, кроме Аткинса, поскольку он основан на предыдущих факторах. Однако целью является способность принимать произвольно большое число и эффективно обрабатывать его для простоты, и int быстро преодолевает произвольное свойство.   -  person Adam    schedule 15.02.2015

Ответы (2)


arrow_upward
2
arrow_downward

Я думаю, что по природе алгоритма нет прямого способа проверить, является ли N простым.

Чтобы проверить, является ли N простым, сначала вы можете использовать простые делители (2, 5, 7 и т. Д.), Затем вы можете сгенерировать все простые числа Аткина под N, а затем попытаться разделить N на каждое простое число Аткина. Если он делится, вы возвращаете false. Если нет, то, боюсь, вам придется проверить все числа под N ....

Возможно, вы можете использовать какой-нибудь вероятностный подход, который может быть гораздо более эффективным для проверки одного числа. Попробуйте такие методы, как Миллера – Рабина или Тест простоты Соловея – Штрассена (используется в RSA).

Думаю, вы будете счастливы: вот реализация Solovay и < a href = "http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=primalityTesting" rel = "nofollow"> очень интересная страница обо всех алгоритмах проверки простоты.

person rducom    schedule 14.02.2015

arrow_upward
3
arrow_downward

Есть несколько связанных проблем, которые следует решать разными способами:

  • Нахождение всех простых множителей данного составного числа: в зависимости от размера для этого следует использовать ро Полларда, метод эллиптической кривой, квадратное сито или сито числового поля. Факторинг чисел в целом занимает много времени.
  • Проверка того, является ли данное число простым: для этого следует использовать метод Миллера-Рабина. Это чрезвычайно быстро и позволяет обойти проблему «разложение чисел на множители происходит медленно», используя характеристику простых чисел, отличную от «тех, которые не имеют нетривиальных множителей».
  • Нахождение всех простых чисел в диапазоне: используйте сито Эратосфена для диапазонов, близких к нулю, или сито Аткина для диапазонов, более удаленных от нуля.

Вы спрашиваете о применении сита Аткина для проверки простоты или разложения числа на простые числа. Это неправильный способ решения любой проблемы.

person tmyklebu    schedule 15.02.2015