# Faster way to get all primes between 0 - n

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

try
{
while (number < goal)
{
if (isPrime(number))
number += 2;
}
}
catch (Exception ex)
{
Console.WriteLine(ex.ToString());
}
finally
{
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 primer.findVersion1(999999);

-
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/… – Prescott Jul 8 '14 at 19:38
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. – Ivo Beckers Jul 9 '14 at 7:21
@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? – WiiMaxx Jul 9 '14 at 7:26
@WiiMaxx, Imagine a divider of a number that is larger than square root of the number. if you then divide the number by that divider you would always get a number smaller then the square root of the number. That number would also be a divider (logically) and would be encountered earlier then. – Ivo Beckers Jul 9 '14 at 7:37
– Ivo Beckers Jul 9 '14 at 8:00

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.

-
would you mind checking out my version and letting me know what you think? codereview.stackexchange.com/q/56500/18427 – Malachi Jul 8 '14 at 21:18
i will check your code when i'm home :) – WiiMaxx Jul 9 '14 at 6:25
very nice thanks – WiiMaxx Jul 9 '14 at 17:55

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

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

Structure
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

-
+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. – WiiMaxx Jul 9 '14 at 6:21