Is there a faster way to get all primes between 0 - n?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace myPrime
    public class simplePrimer
        public List<BigInteger> primeList;

        public void findVersion(BigInteger goal)
            BigInteger number = 3;
            primeList = new List<BigInteger> { 2 };

                while (number < goal)
                    if (isPrime(number))
                    number += 2;
            catch (Exception ex)
                Console.WriteLine("i found " + primeList.Count + " Prime Numbers");
                Console.WriteLine(primeList.Last() + "was the last Prime");

        private bool isPrime(BigInteger number)
            foreach (BigInteger prime in primeList)
                if (number % prime == 0)
                    return false;

            return true;

You can call it like:

  • 5
    \$\begingroup\$ You're going to want to find a non naïve prime algorithm. Check out this answer on Stackoverflow that will help you stackoverflow.com/questions/3220907/… \$\endgroup\$ – Prescott Jul 8 '14 at 19:38
  • 1
    \$\begingroup\$ To speed it up a lot, especially for a large goal, don't check each prime in primeList in the isPrime method but only primes that are less then the square root of the number. \$\endgroup\$ – Ivo Beckers Jul 9 '14 at 7:21
  • \$\begingroup\$ @IvoBeckers why do i only need to check primes which are less then the square root of the number, wouldn't i miss some Primes? \$\endgroup\$ – WiiMaxx Jul 9 '14 at 7:26
  • 1
    \$\begingroup\$ check stackoverflow.com/questions/5811151/… \$\endgroup\$ – Ivo Beckers Jul 9 '14 at 8:00
  • 1
    \$\begingroup\$ @Gabe sure but you can hold bigger number with it \$\endgroup\$ – WiiMaxx Jul 9 '14 at 11:49

For relatively small numbers, the best method is very likely the Sieve of Erathostenes.

Here's a method I wrote a few years ago that implements it. A useful thing to do is to use a BitArray; it will save a lot of space. It also skips even numbers to save even more space. I also made it return each number in sequence instead of returning a List.

Finding prime numbers up to int.MaxValue takes about 45 seconds (and uses +/- 130Mb of memory). Using 1 million as bound will be lightning fast, though. It can be done faster still, but the code would become more complex.

public static IEnumerable<int> Primes(int bound)
    if (bound < 2) yield break;
    //The first prime number is 2
    yield return 2;

    BitArray composite = new BitArray((bound - 1) / 2);
    int limit = ((int)(Math.Sqrt(bound)) - 1) / 2;
    for (int i = 0; i < limit; i++) {
        if (composite[i]) continue;
        //The first number not crossed out is prime
        int prime = 2 * i + 3;
        yield return prime;
        //cross out all multiples of this prime, starting at the prime squared
        for (int j = (prime * prime - 2) >> 1; j < composite.Count; j += prime) {
            composite[j] = true;
    //The remaining numbers not crossed out are also prime
    for (int i = limit; i < composite.Count; i++) {
        if (!composite[i]) yield return 2 * i + 3;

For larger numbers, you need more advanced techniques. A popular one is the Miller-Rabin primality test.


Leaving aside the algorithm there are a number of points about the code

Pascal casing is standard for C# - SimplePrimer and FindVersion as opposed to simplePrimer and findVersion.
FindVersion seems unconnected to the functionality.

public fields are generally frowned upon. If it needs to be part of the interface, make it a Property so that the implementation can be changed if needed.
Having a separate 'return' as PrimeList seems overly complicated. There is no strong reason for not having List<BigInteger> GetPrimes(BigInteger goal)
Looking at the code, I cannot see anything obvious that might throw an exception that might be caught by the catch (perhaps an out of range on the BigInteger?) Is it needed?
As a shape I would push for any output to be external to the function. Have the calling code catch errors or report results. It makes unit testing a lot simpler

  • \$\begingroup\$ +1 I totally agree with all your points so will change that. The naming of my methode findVersionis because i had multiple versions of find. But in the end i was really just looking for a performance improvement so i can't accept your answer, sry. \$\endgroup\$ – WiiMaxx Jul 9 '14 at 6:21

protected by Malachi Dec 14 '16 at 14:23

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.