Каков наилучший, наиболее производительный алгоритм для нахождения всех простых чисел до заданного числа? - PullRequest
Новая
       1

Каков наилучший, наиболее производительный алгоритм для нахождения всех простых чисел до заданного числа?

2 голосов
/ 03 ноября 2011

В настоящее время у меня есть этот метод, который отлично работает: 

 private static List<long> GetPrimeNumbers(long number)
        {
            var result = new List<long>();
            for (var i = 0; i <= number; i++)
            {
                var isPrime = true;
                for (var j = 2; j < i; j++) 
                {
                    if (i % j == 0) 
                    {
                        isPrime = false;
                        break;
                    }
                }
                if (isPrime)
                {
                    result.Add(i);
                }
            }
            return result;
        }

Является ли приведенный выше лучший алгоритм из возможных?

Это действительно медленно, когда число превышает 100000.

Я имею в виду, что будет лучшим, наиболее эффективным алгоритмом для нахождения простых чисел, меньших или равных данному числу?

Ответы [ 7 ]

5 голосов
/ 03 ноября 2011

  1. Сито Эратосфен .Этот алгоритм может генерировать все простые числа до n.Сложность по времени - O(nlog(n)), сложность памяти - O(n)

  2. Проверка простоты BPSW .Этот алгоритм может проверить, является ли n псевдослучайным .Это было проверено на первых 10 ^ 15 числах.Временная сложность - O(log(n)).

ОБНОВЛЕНИЕ: Я провел небольшое исследование и написал простую реализацию генерации простых чисел в c #.Основная идея, когда мы проверяем число N на простоту - нам просто нужно проверить, делится ли оно на любое простое число, которое меньше sqrt(N).

Первая реализация: 

public static List<int> GeneratePrimes(int n)
{
  var primes = new List<int>();
  for(var i = 2; i <= n; i++)
  {
    var ok = true;
    foreach(var prime in primes)
    {
      if (prime * prime > i)
        break;
      if (i % prime == 0)
      {
        ok = false;
        break;
      }
    }
    if(ok)
      primes.Add(i);
  }
  return primes;
}

Результаты теста : 

10^6 - 0.297s
10^7 - 6.202s
10^8 - 141.860s

Вторая реализация с использованием параллельных вычислений: 1. Генерация всех простых чисел до sqrt(N) 2. Генерация всех простых чисел от sqrt(N) + 1 до N с использованием простых чисел доsqrt(N) с использованием параллельных вычислений. 

public static List<int> GeneratePrimesParallel(int n)
    {
      var sqrt = (int) Math.Sqrt(n);
      var lowestPrimes = GeneratePrimes(sqrt);
      var highestPrimes =  (Enumerable.Range(sqrt + 1, n - sqrt)
                                .AsParallel()
                                .Where(i => lowestPrimes.All(prime => i % prime != 0)));
      return lowestPrimes.Concat(highestPrimes).ToList();
    }

Результаты испытаний : 

10^6 - 0.276s
10^7 - 4.082s
10^8 - 78.624
4 голосов
/ 03 ноября 2011

Вероятно, Сито Аткина является наиболее эффективным, хотя, насколько я знаю, с тех пор кто-то нашел лучшее.

Erathosthenes и Sundaram также имеют свои собственные сита, которые значительно проще в реализации. Любой из них избавляется от необходимости делать это путем отдельного поиска коэффициента в каждом числе до предела.

Все сита используют больше рабочей памяти, чем разлагаются по одному значению за раз, но, как правило, все еще меньше памяти, чем результирующий список простых чисел.

2 голосов
/ 03 ноября 2011

Вы можете существенно улучшить свой алгоритм тестирования, если n кратно любому целому числу от 2 до sqrt (n). 

    private static List<int> GetPrimeNumbers2(long number)
    {
        var result = new List<int>();

        for (var i = 0; i <= number; i++)
        {
            var isPrime = true;
            var n = Math.Floor(Math.Sqrt(i));

            for (var j = 2; j <= n; j++)
            {
                if (i % j == 0)
                {
                    isPrime = false;
                    break;
                }
            }

            if (isPrime)
            {
                result.Add(i);
            }
        }

        return result;
    }

Это меняет сложность с O (N N) на O(N sqrt (N)).

Самым быстрым из известных алгоритмов проверки простоты общих чисел является Доказательство первичности эллиптической кривой (ECPP): http://en.wikipedia.org/wiki/Elliptic_curve_primality_provingЯ думаю, что реализовать это будет сложно, поэтому делайте это только в том случае, если вам это действительно нужно.Вероятно, здесь есть библиотека, которая может вам помочь.

1 голос
/ 03 ноября 2011

Это даст вам разумную производительность для начального выполнения, а затем приблизится к O (1) (это будет O (N), но очень, очень, мало) производительности для любых повторных запросов и разумной производительности для значений, превышающихтекущее максимальное число видимых. 

private static List<ulong> KnownPrimes = new List<ulong>();
private static ulong LargestValue = 1UL;


private static List<ulong> GetFastestPrimeNumbers(ulong number)
{
    var result = new List<ulong>();
    lock (KnownPrimes)
    {
        result.AddRange(KnownPrimes.Where(c => c < number).ToList());
        if (number <= LargestValue)
        {
            return result;
        }
        result = KnownPrimes;

        for (var i = LargestValue + 1; i <= number; i++)
        {
            var isPrime = true;
            var n = Math.Floor(Math.Sqrt(i));

            for (var j = 0; j < KnownPrimes.Count; j++)
            {
                var jVal = KnownPrimes[j];
                if (jVal * jVal > i)
                {
                    //isPrime = false;
                    break;
                }
                else if (i % jVal == 0)
                {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime)
            {
                result.Add(i);
            }
        }
        LargestValue = number;
    }
    return result;

}

Редактировать: Значительно быстрее, используя Sieve of Atkin, который я добавил в konw по поводу: 

private static List<ulong> KnownPrimes = new List<long>();
private static ulong LargestValue = 1UL;

private unsafe static List<ulong> FindPrimes(ulong number)
{
    var result = new List<ulong>();
    var isPrime = new bool[number + 1];
    var sqrt = Math.Sqrt(number);
    lock (KnownPrimes)
    {

        fixed (bool* pp = isPrime)
        {
            bool* pp1 = pp;
            result.AddRange(KnownPrimes.Where(c => c < number).ToList());
            if (number <= LargestValue)
            {
                return result;
            }
            result = KnownPrimes;

            for (ulong x = 1; x <= sqrt; x++)
                for (ulong y = 1; y <= sqrt; y++)
                {
                    var n = 4 * x * x + y * y;
                    if (n <= number && (n % 12 == 1 || n % 12 == 5))
                        pp1[n] ^= true;

                    n = 3 * x * x + y * y;
                    if (n <= number && n % 12 == 7)
                        pp1[n] ^= true;

                    n = 3 * x * x - y * y;
                    if (x > y && n <= number && n % 12 == 11)
                        pp1[n] ^= true;
                }

            for (ulong n = 5; n <= sqrt; n++)
                if (pp1[n])
                {
                    var s = n * n;
                    for (ulong k = s; k <= number; k += s)
                        pp1[k] = false;
                }

            if (LargestValue < 3)
            {
                KnownPrimes.Add(2);
                KnownPrimes.Add(3);
            }
            for (ulong n = 5; n <= number; n += 2)
                if (pp1[n])
                    KnownPrimes.Add(n);
            LargestValue = number;
        }
    }

    return result;
}

Адаптировано из Источник

Это можно легко улучшить, чтобы повысить производительность при добавлении элементов, но я бы посоветовал вам сохранять предыдущий список KnownPrimes на диске между выполнениями и загружать существующий список значений, например, список из http://primes.utm.edu/lists/small/millions - Кредит поступает в CodingBarfield

0 голосов
/ 03 ноября 2011

Я думаю, что уместным вопросом является «насколько велика будет верхняя граница».Если число находится в относительно небольшом диапазоне [допустим, 2 ^ 16], вы, вероятно, можете просто предварительно вычислить и сохранить все простые числа (ниже некоторого предела) в файл, а затем загрузить их в память, где это необходимо (и затем потенциально продолжить использовать один изСита, перечисленные ниже.

Иван Бенко и Стив Джессоп выше описывают два более известных быстрых метода [Eratosthenes, Atkin], хотя Иван, сложность сита O (n * log (log (n)))).

Сито относительно легко внедрить и очень быстро по сравнению с вашим методом.

0 голосов
/ 03 ноября 2011

Я нашел эту ссылку:

http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm

в соответствии с вашим вопросом, кажется, что вас интересует не доказательство того, что определенное число, вероятно, (или, конечно,) простое число, и ни вы не заинтересованы в факторинге больших чисел.Чтобы найти все простые числа до заданного N, можно использовать сито Эратосфена, но, похоже, в приведенной выше ссылке были рассмотрены дальнейшие оптимизации.

0 голосов
/ 03 ноября 2011

Абсолютный самый производительный:

(сверните работу, чтобы получить результат).

Сохраните простые числа всех чисел в домене в хеш-таблице с номером в качестве ключа.

...