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.