# Computation of primality

I believe I have achieved computation of primality! That is, the computation of prime numbers. The code I am about to post will give you every prime there is, in order, starting with 2. Can we call this a major win guys?

Edit: just to be clear guys, this is a general formula for the computation of primality! (one which we didn't know existed and one which, well, I get the feeling we were about to prove wrong).

What I mean by this, is you can pass a LinkedList of the first 25 million primes, and the NextPrime() method will give you the 25,000,001 prime. And you can keep on calling NextPrime() to keep going up! You can start with a list almost as big as a LinkedList will hold (unfortunately, I think that means we are limited to computing up to the first 2 billion primes. We can get around that with a little custom data structure coding)

using System;
using System.Collections.Generic;
using System.Linq;

public class PrimeTester
{
public virtual bool RelativelyPrime(IEnumerable<long> numbers, bool onlyCheckLast)
{
if (onlyCheckLast)
{
var squareRoot = (long)Math.Sqrt(numberToCheck);

.All(number => numberToCheck % number > 0);
}

while (true)
{
{
return true;
}

if (orderedLinkedList.Any(number => number%lowestNumber == 0))
{
return false;
}
}
}
}


onlyCheckLast is true for computing primes (all the previous primes must be stored in an ordered set). If you want to pass in a full set of any kind of whole number, then you can always pass false to onlyCheckLast.

(Isn't that modulo arithmetic nice?) Here is the actual prime generator:

using System;
using System.Collections.Generic;
using System.Linq;

public class PrimeGenerator
{
public PrimeGenerator()
{
this.tester = new PrimeTester();
this.currentSet = new LinkedList<long>(new long[] { 2, 3 });
}

{
this.tester = new PrimeTester();
this.currentSet = currentSet;
}

public virtual long NextPrime()
{
return this.collectPrime();
}

public virtual IEnumerable<long> Generate()
{
foreach (var prime in this.currentSet)
{
yield return prime;
}

while (true)
{
yield return this.collectPrime();
}
}

private long collectPrime()
{
while (!this.tester.RelativelyPrime(this.currentSet, true))
{
var node = this.currentSet.Last;
this.currentSet.RemoveLast();
}

return this.currentSet.Last.Value;
}