What is the best, most performant algorithm to find all primes up to a given number?

Question

I'm currently having this method which works fine:

 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;
        }

Is the above the best algorithm possible?

It's really slow when the number is above 100000.

I mean, what'd be the best, most performant algorithm to find the prime numbers less than or equal to a given number?

Answer 1

1. Sieve of Eratosthenes. This algorithm can generate all prime numbers up to n. Time complexity - O(nlog(n)), memory complexity - O(n)

2. BPSW primality test. This algorithm can check if n is pseudoprime. It was tested on first 10^15 numbers. Time complexity - O(log(n)).

UPDATE: I did some research and wrote simple implementation of generating prime numbers in c#. Main idea when we check number N for primality - we just need to check if it divisible by any prime number that less than sqrt(N).

First implementation:

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;
}

Test results:

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

Second implementation using parallel computing: 1. Generate all primes up to sqrt(N) 2. Generate all primes from sqrt(N) + 1 to N using primes up to sqrt(N) using parallel computing.

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();
    }

Test results:

10^6 - 0.276s
10^7 - 4.082s
10^8 - 78.624

Answer 2

Probably the Sieve of Atkin is most performant, although for all I know somebody found a better once since.

Erathosthenes and Sundaram also have sieves of their own, which are considerably simpler to implement. Any of them kicks the stuffing out of doing it by separately looking for a factor in each number up to the limit.

All sieves use more working memory than factorizing one value at a time, but generally still less memory than the resulting list of primes.

Answer 3

You can improve substantially your algorithm testing whether n is a multiple of any integer between 2 and 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;
    }

This change the complexity from O(NN) to O(Nsqrt(N)).

The fastest known algorithm for testing the primality of general numbers is the Elliptic Curve Primality Proving (ECPP): http://en.wikipedia.org/wiki/Elliptic_curve_primality_proving I guess that implementing it will be difficult so do it only if you really need it. There are probably library that could help you here.

Answer 4

This will give you reasonable performance for the initial execution and then near to O(1) (it will be O(N) but very, very, small) performance for any repeated requests, and reasonable performance for values larger than the current max number seen.

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;

}

Edit: Considerably faster using Sieve of Atkin, which I addapted to konw about the:

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;
}

Adapted from Source

This can easily be improved to get better performance when adding items, but I would suggest you save the previous KnownPrimes list to disk between executions, and load a pre-existing list of values such as the list from http://primes.utm.edu/lists/small/millions – Credit goes to CodingBarfield

Answer 5

I found this link:

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

according to your question, it seems that what you are interested in is not in proving that a certain given number is probably (or certainly) a prime, and neither you are interested in factoring large numbers. To find all prime numbers up to a given N, one can use Eratosthenes Sieve, but it seems that in the link above further optimizations were considered.

Answer 6

I think a pertinent question is "how big will the upper limit ever be". If the number is in a relatively small range [lets say 2^16] you could probably just precompute and save all the primes (below some limit) to file, and then load into memory where appropriate (and then potentially continue using one of the Sieves listed below.

Ivan Benko and Steve Jessop above do state the two more well known fast methods [Eratosthenes, Atkin] although Ivan, the complexity of the Sieve is O(n*log(log(n))).

The Sieve is relatively easy to implement and is very fast compared to your method.

Answer 7

The absolute most performant:

(Minimize the work to get the result).

Store the primes of all numbers in the domain in a hashtable with the number as key.