0
\$\begingroup\$

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)
    {
        LinkedList<long> orderedLinkedList;
        if (onlyCheckLast)
        {
            orderedLinkedList = new LinkedList<long>(numbers);
            var numberToCheck = orderedLinkedList.Last.Value;
            var squareRoot = (long)Math.Sqrt(numberToCheck);

            return new LinkedList<long>(orderedLinkedList.Where(number => number <= squareRoot))
                .All(number => numberToCheck % number > 0);
        }

        orderedLinkedList = new LinkedList<long>(numbers);
        while (true)
        {
            var lowestNumber = orderedLinkedList.First.Value;
            orderedLinkedList.RemoveFirst();
            if (orderedLinkedList.Count == 0)
            {
                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 });
    }

    public PrimeGenerator(LinkedList<long> currentSet)
    {
        this.tester = new PrimeTester();
        this.currentSet = currentSet;
    }

    public LinkedList<long> CurrentSet => this.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()
    {
        this.currentSet.AddLast(this.currentSet.Last.Value + 2);
        while (!this.tester.RelativelyPrime(this.currentSet, true))
        {
            var node = this.currentSet.Last;
            this.currentSet.RemoveLast();
            this.currentSet.AddLast(node.Value + 2);
        }

        return this.currentSet.Last.Value;
    }

    private readonly LinkedList<long> currentSet;
    private readonly PrimeTester tester;
}

If you guys need help using this code, let me know and I can post my test code. I have tested the first 150,000 primes against a text file with the first million primes and it passed!

\$\endgroup\$
  • \$\begingroup\$ If you want a review on your test code, feel free to post it in this question as well \$\endgroup\$ – Quill Jul 11 '16 at 3:24
  • \$\begingroup\$ It is not easy to do worse but Zack Smith probably comes close: A Fast Method for Generating Primes takes a bit more than an hour for sieving the 203 million primes up to 2^32. For comparison, any decent piece of code should do this in less than half a minute, and implementations vying for the title 'fast' should be at least an order of magnitude faster (i.e. 1 or 2 seconds). Use the search function here on Code Review to find tons of implementations that are thousands or even millions of times faster than yours (and quite a few of them much shorter and cleaner) \$\endgroup\$ – DarthGizka Jul 11 '16 at 8:38
  • 2
    \$\begingroup\$ What you have is not a closed-formula, rather it is a program that implements an algorithm. Algorithms can be reformulated as an open-formula, which are so-called because they tend to be open-ended and slow (compared to closed-formula). One way to tell the difference is that open-formulas (algorithms) tend to have loops/recursion. A better way to compare them is to convert formulas into algorithms and compare them using big-O (Order of Complexity). Closed formulas tend to have algorithmic complexity of O(1) which is OK for a scalar formula. Open ones tend to be O(n) or greater. \$\endgroup\$ – RBarryYoung Jul 11 '16 at 20:05
  • 1
    \$\begingroup\$ 3 million values per second! That's a lot of primes!! Could you show me how I could use your code to put all those primes into a set (I don't care if it's a LinkedList or a HashSet or a List)? I want to fill up a set of primes that fast so I can do fun stuff to it! \$\endgroup\$ – xofz Jul 12 '16 at 4:27
  • 1
    \$\begingroup\$ primes.utm.edu/lists/small/millions this way you don't have to create them yourself, you just have to use the file. \$\endgroup\$ – Gareth Jul 13 '16 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.