Most elegant way to generate prime numbers [closed]

Question

What is the most elegant way to implement this function:

ArrayList generatePrimes(int n)

This function generates the first n primes (edit: where n>1), so generatePrimes(5) will return an ArrayList with {2, 3, 5, 7, 11}. (I'm doing this in C#, but I'm happy with a Java implementation - or any other similar language for that matter (so not Haskell)).

I do know how to write this function, but when I did it last night it didn't end up as nice as I was hoping. Here is what I came up with:

ArrayList generatePrimes(int toGenerate)
{
    ArrayList primes = new ArrayList();
    primes.Add(2);
    primes.Add(3);
    while (primes.Count < toGenerate)
    {
        int nextPrime = (int)(primes[primes.Count - 1]) + 2;
        while (true)
        {
            bool isPrime = true;
            foreach (int n in primes)
            {
                if (nextPrime % n == 0)
                {
                    isPrime = false;
                    break;
                }
            }
            if (isPrime)
            {
                break;
            }
            else
            {
                nextPrime += 2;
            }
        }
        primes.Add(nextPrime);
    }
    return primes;
}

I'm not too concerned about speed, although I don't want it to be obviously inefficient. I don't mind which method is used (naive or sieve or anything else), but I do want it to be fairly short and obvious how it works.

Edit: Thanks to all who have responded, although many didn't answer my actual question. To reiterate, I wanted a nice clean piece of code that generated a list of prime numbers. I already know how to do it a bunch of different ways, but I'm prone to writing code that isn't as clear as it could be. In this thread a few good options have been proposed:

• A nicer version of what I originally had (Peter Smit, jmservera and Rekreativc)
• A very clean implementation of the sieve of Eratosthenes (starblue)
• Use Java's BigIntegers and nextProbablePrime for very simple code, although I can't imagine it being particularly efficient (dfa)
• Use LINQ to lazily generate the list of primes (Maghis)
• Put lots of primes in a text file and read them in when necessary (darin)

Edit 2: I've implemented in C# a couple of the methods given here, and another method not mentioned here. They all find the first n primes effectively (and I have a decent method of finding the limit to provide to the sieves).

Horsey

it would be better in order to me retutning ienumerable<int> and yielding one by one – Typescript

What I would like to know is what is the least elegant way to generate prime numbers. I'm thinking something involving an Access database? – Trochee

for comparison, a 2008 Haskell code by BMeph: nubBy (((>1).).gcd) [2..]. It leaves only non-duplicates among the natural numbers, starting from 2, while considering as duplicate any number whose gcd with any of the previously found numbers is greater than 1. It is very inefficient, quadratic in number of primes produced. But it is elegant. – Pottle

the most elegant, IMO, is Haskell's import Data.List.Ordered ; let { _Y g = g (_Y g) ; primes = 2 : _Y( (3:) . minus [5,7..] . unionAll . map (\p-> [p*p, p*p+p*2..]) ) } but that is of course entirely opinion based. – Pottle

What kind of prime numbers are you looking for? What tests should they pass? – Clipped

Answer 1

Many thanks to all who gave helpful answers. Here are my implementations of a few different methods of finding the first n primes in C#. The first two methods are pretty much what was posted here. (The posters names are next to the title.) I plan on doing the sieve of Atkin sometime, although I suspect it won't be quite as simple as the methods here currently. If anybody can see any way of improving any of these methods I'd love to know :-)

Standard Method (Peter Smit, jmservera, Rekreativc)

The first prime number is 2. Add this to a list of primes. The next prime is the next number that is not evenly divisible by any number on this list.

public static List<int> GeneratePrimesNaive(int n)
{
    List<int> primes = new List<int>();
    primes.Add(2);
    int nextPrime = 3;
    while (primes.Count < n)
    {
        int sqrt = (int)Math.Sqrt(nextPrime);
        bool isPrime = true;
        for (int i = 0; (int)primes[i] <= sqrt; i++)
        {
            if (nextPrime % primes[i] == 0)
            {
                isPrime = false;
                break;
            }
        }
        if (isPrime)
        {
            primes.Add(nextPrime);
        }
        nextPrime += 2;
    }
    return primes;
}

This has been optimised by only testing for divisibility up to the square root of the number being tested; and by only testing odd numbers. This can be further optimised by testing only numbers of the form 6k+[1, 5], or 30k+[1, 7, 11, 13, 17, 19, 23, 29] or so on.

Sieve of Eratosthenes (starblue)

This finds all the primes to k. To make a list of the first n primes, we first need to approximate value of the nth prime. The following method, as described here, does this.

public static int ApproximateNthPrime(int nn)
{
    double n = (double)nn;
    double p;
    if (nn >= 7022)
    {
        p = n * Math.Log(n) + n * (Math.Log(Math.Log(n)) - 0.9385);
    }
    else if (nn >= 6)
    {
        p = n * Math.Log(n) + n * Math.Log(Math.Log(n));
    }
    else if (nn > 0)
    {
        p = new int[] { 2, 3, 5, 7, 11 }[nn - 1];
    }
    else
    {
        p = 0;
    }
    return (int)p;
}

// Find all primes up to and including the limit
public static BitArray SieveOfEratosthenes(int limit)
{
    BitArray bits = new BitArray(limit + 1, true);
    bits[0] = false;
    bits[1] = false;
    for (int i = 0; i * i <= limit; i++)
    {
        if (bits[i])
        {
            for (int j = i * i; j <= limit; j += i)
            {
                bits[j] = false;
            }
        }
    }
    return bits;
}

public static List<int> GeneratePrimesSieveOfEratosthenes(int n)
{
    int limit = ApproximateNthPrime(n);
    BitArray bits = SieveOfEratosthenes(limit);
    List<int> primes = new List<int>();
    for (int i = 0, found = 0; i < limit && found < n; i++)
    {
        if (bits[i])
        {
            primes.Add(i);
            found++;
        }
    }
    return primes;
}

Sieve of Sundaram

I only discovered this sieve recently, but it can be implemented quite simply. My implementation isn't as fast as the sieve of Eratosthenes, but it is significantly faster than the naive method.

public static BitArray SieveOfSundaram(int limit)
{
    limit /= 2;
    BitArray bits = new BitArray(limit + 1, true);
    for (int i = 1; 3 * i + 1 < limit; i++)
    {
        for (int j = 1; i + j + 2 * i * j <= limit; j++)
        {
            bits[i + j + 2 * i * j] = false;
        }
    }
    return bits;
}

public static List<int> GeneratePrimesSieveOfSundaram(int n)
{
    int limit = ApproximateNthPrime(n);
    BitArray bits = SieveOfSundaram(limit);
    List<int> primes = new List<int>();
    primes.Add(2);
    for (int i = 1, found = 1; 2 * i + 1 <= limit && found < n; i++)
    {
        if (bits[i])
        {
            primes.Add(2 * i + 1);
            found++;
        }
    }
    return primes;
}

Horsey

FYI - I had to change your main loop counter to "for (int i = 0; i * i <= limit && i * i > 0; i++)" in order to prevent an overflow. – Missilery

This implementation of the Sieve of Sundaram is one of the very few correct ones out there. Most of them use wrong bounds for i and j while calculating i+j+2*i*j leading to incorrect output. – Melnick

Answer 2

Use the estimate

pi(n) = n / log(n)

for the number of primes up to n to find a limit, and then use a sieve. The estimate underestimates the number of primes up to n somewhat, so the sieve will be slightly larger than necessary, which is ok.

This is my standard Java sieve, computes the first million primes in about a second on a normal laptop:

public static BitSet computePrimes(int limit)
{
    final BitSet primes = new BitSet();
    primes.set(0, false);
    primes.set(1, false);
    primes.set(2, limit, true);
    for (int i = 0; i * i < limit; i++)
    {
        if (primes.get(i))
        {
            for (int j = i * i; j < limit; j += i)
            {
                primes.clear(j);
            }
        }
    }
    return primes;
}

Wilding

That's a very nice implementation of the sieve of Eratosthenes – Horsey

shoultn't it be enough to loop while i <= Math.sqrt(limit) in the outer loop? – Sinew

@Sinew Yes, it is ok, and the floating point precision is good enough to represent the relevant integers exactly. It reduces runtime by about 20%, so I changed it. – Wilding

I'd expect that it would reduce runtime even more if you either calculate Math.sqrt(limit) outside the loop instead of calculating it in each iteration, or change the iteration condition to i*i<=limit. Do they, and by how much? – Merchandise

Ok, updated to next version. :-) With the tighter bound we don't need long in the inner loop, which saves another 10 to 15% runtime. i * i <= limit is minimally faster than i < Math.sqrt(limit), I think because it does the comparison in integers and avoids conversion to floating point. Extracting the sqrt and casting to in is the same, extracting sqrt but not casting to int gains nothing. – Wilding

The estimate pi(n) = n / log(n) underestimates the nth prime, so the sieve will be smaller than necessary. Luckily, I've worked out a better way of doing it: #1043217 – Horsey

@David Johnstone No, pi(n) = n / log(n) underestimates the number of primes up to n, which goes in the opposite direction. I'm glad you found a much nicer approximation, though. – Wilding

if you are willing to remove all of the multiples of 2 in its own loop, you can use j+= 2 * i as your loop increment to save some extra runtime, and you can calculate that once using a bit shift – Oceanography

By replacing BitSet by a class implementing wheel factorization for 2, 3 and 5 it becomes almost 3 times faster. – Wilding

Answer 3

Ressurecting an old question, but I stumbled over it while playing with LINQ.

This Code Requires .NET4.0 or .NET3.5 With Parallel Extensions

public List<int> GeneratePrimes(int n) {
    var r = from i in Enumerable.Range(2, n - 1).AsParallel()
            where Enumerable.Range(1, (int)Math.Sqrt(i)).All(j => j == 1 || i % j != 0)
            select i;
    return r.ToList();
}

Unplumbed

Why isn't this the accepted answer? The code here is much shorter, more elegant and way faster than the code in the accepted answer. Wish I could upvote more than once! – Sjambok

shorter code does not mean better. If that were true, we'd all be writing Perl. – Valladolid

This is the sort of solution I would have done, if I wasn't so lazy that I searched for it first. Just FYI, this runs just fine under .NET 8. – Sthenic

Answer 4

You are on the good path.

Some comments

• primes.Add(3); makes that this function doesn't work for number = 1

• You dont't have to test the division with primenumbers bigger that the squareroot of the number to be tested.

Suggested code:

ArrayList generatePrimes(int toGenerate)
{
    ArrayList primes = new ArrayList();

    if(toGenerate > 0) primes.Add(2);

    int curTest = 3;
    while (primes.Count < toGenerate)
    {

        int sqrt = (int) Math.sqrt(curTest);

        bool isPrime = true;
        for (int i = 0; i < primes.Count && primes.get(i) <= sqrt; ++i)
        {
            if (curTest % primes.get(i) == 0)
            {
                isPrime = false;
                break;
            }
        }

        if(isPrime) primes.Add(curTest);

        curTest +=2
    }
    return primes;
}

Cineraria

testing that prime*prime <= curTest in the loop instead of pre-calculating the square root will probably make it faster and will make it more generic (will work for bignums, etc) – Aili

Why using the square root? What's the mathematical background for such option? I, probably dully, would only divide by 2. – Homotaxis

Because if a number has prime factors, at least one of them must be less than or equal to the square root. If a * b = c and a <= b then a <= sqrt(c) <= b. – Horsey

Answer 5

you should take a look at probable primes. In particular take a look to Randomized Algorithms and Miller–Rabin primality test.

For the sake of completeness you could just use java.math.BigInteger:

public class PrimeGenerator implements Iterator<BigInteger>, Iterable<BigInteger> {

    private BigInteger p = BigInteger.ONE;

    @Override
    public boolean hasNext() {
        return true;
    }

    @Override
    public BigInteger next() {
        p = p.nextProbablePrime();
        return p;
    }

    @Override
    public void remove() {
        throw new UnsupportedOperationException("Not supported.");
    }

    @Override
    public Iterator<BigInteger> iterator() {
        return this;
    }
}

@Test
public void printPrimes() {
    for (BigInteger p : new PrimeGenerator()) {
        System.out.println(p);
    }
}

Beshore

Miller-Rabbin is very fast and the code is very simple. Giving it sufficient iterations makes it reliable enough to be in competition with random CPU failure in terms of likelihood of a false positive. The downside of the algorithm is that understanding why it actually works is a difficult task. – Interlocutress

Answer 6

By no means effecient, but maybe the most readable:

public static IEnumerable<int> GeneratePrimes()
{
   return Range(2).Where(candidate => Range(2, (int)Math.Sqrt(candidate)))
                                     .All(divisor => candidate % divisor != 0));
}

with:

public static IEnumerable<int> Range(int from, int to = int.MaxValue)
{
   for (int i = from; i <= to; i++) yield return i;
}

In fact just a variation of some posts here with nicer formatting.

Sita

Answer 7

Copyrights 2009 by St.Wittum 13189 Berlin GERMANY under CC-BY-SA License https://creativecommons.org/licenses/by-sa/3.0/

The simple but most elegant way to compute ALL PRIMES would be this, but this way is slow and memory costs are much higher for higher numbers because using faculty (!) function ... but it demonstrates a variation of Wilson Theoreme in an application to generate all primes by algorithm implemented in Python

#!/usr/bin/python
f=1 # 0!
p=2 # 1st prime
while True:
    if f%p%2:
        print p
    p+=1
    f*=(p-2)

Chouinard

Answer 8

I can offer the following C# solution. It's by no means fast, but it is very clear about what it does.

public static List<Int32> GetPrimes(Int32 limit)
{
    List<Int32> primes = new List<Int32>() { 2 };

    for (int n = 3; n <= limit; n += 2)
    {
        Int32 sqrt = (Int32)Math.Sqrt(n);

        if (primes.TakeWhile(p => p <= sqrt).All(p => n % p != 0))
        {
            primes.Add(n);
        }
    }

    return primes;
}

I left out any checks - if limit is negative or smaller than two (for the moment the method will allways at least return two as a prime). But that's all easy to fix.

UPDATE

Withe the following two extension methods

public static void Do<T>(this IEnumerable<T> collection, Action<T> action)
{
    foreach (T item in collection)
    {
        action(item);
    }
}

public static IEnumerable<Int32> Range(Int32 start, Int32 end, Int32 step)
{
    for (int i = start; i < end; i += step)
    }
        yield return i;
    }
}

you can rewrite it as follows.

public static List<Int32> GetPrimes(Int32 limit)
{
    List<Int32> primes = new List<Int32>() { 2 };

    Range(3, limit, 2)
        .Where(n => primes
            .TakeWhile(p => p <= Math.Sqrt(n))
            .All(p => n % p != 0))
        .Do(n => primes.Add(n));

    return primes;
}

It's less efficient (because the square root as reevaluated quite often) but it is even cleaner code. It is possible to rewrite the code to lazily enumerate the primes, but this will clutter the code quite a bit.

Typo

I'm nearly positive that the calculation of the square root is optimized out by the JIT compiler (when compiled with optimization enabled). You'd have to verify this by examining the assembly generated (the IL is only partially optimized and is nowhere near the optimization performed by the JIT compiler. The days of loop hoisting and other micro optimizations are way over. In fact, sometimes trying to outsmart the JIT can slow down your code. – Insignificancy

Answer 9

Here's an implementation of Sieve of Eratosthenes in C#:

    IEnumerable<int> GeneratePrimes(int n)
    {
        var values = new Numbers[n];

        values[0] = Numbers.Prime;
        values[1] = Numbers.Prime;

        for (int outer = 2; outer != -1; outer = FirstUnset(values, outer))
        {
            values[outer] = Numbers.Prime;

            for (int inner = outer * 2; inner < values.Length; inner += outer)
                values[inner] = Numbers.Composite;
        }

        for (int i = 2; i < values.Length; i++)
        {
            if (values[i] == Numbers.Prime)
                yield return i;
        }
    }

    int FirstUnset(Numbers[] values, int last)
    {
        for (int i = last; i < values.Length; i++)
            if (values[i] == Numbers.Unset)
                return i;

        return -1;
    }

    enum Numbers
    {
        Unset,
        Prime,
        Composite
    }

Soche

i'd do that with a bool instead of enum... – Erinn

Answer 10

Use a prime numbers generator to create primes.txt and then:

class Program
{
    static void Main(string[] args)
    {
        using (StreamReader reader = new StreamReader("primes.txt"))
        {
            foreach (var prime in GetPrimes(10, reader))
            {
                Console.WriteLine(prime);
            }
        }
    }

    public static IEnumerable<short> GetPrimes(short upTo, StreamReader reader)
    {
        int count = 0;
        string line = string.Empty;
        while ((line = reader.ReadLine()) != null && count++ < upTo)
        {
            yield return short.Parse(line);
        }
    }
}

In this case I use Int16 in the method signature, so my primes.txt file contains numbers from 0 to 32767. If you want to extend this to Int32 or Int64 your primes.txt could be significantly larger.

Kumquat

I'm sure its very elegant to just read primes from a file, however I don't think this is really relevant to the question. He is probably more interested in how you generate the numbers in prime number generator... – Viper

Citing the OP: "I don't mind which method is used (naive or sieve or anything else), but I do want it to be fairly short and obvious how it works". I think my answer is perfectly relevant. It is also the fastest method. – Kumquat

Even if he says "I don't mind which method..." I don't think that includes "open a list of primes". That would be like answering the question "how to build a computer" by "buy a computer". -1 – Ottoottoman

It is only the fastest for big primes - for small numbers the tight loop is much much faster. – Switzerland

It would be faster if you actually wrote the prime numbers in the source code itself, instead of reading them from a file. – Taxaceous

Writing them in the source file would consume too much memory. – Kumquat

Consume much memory? more than reading the full primes list as text into... memory? Do you know how strings work in .net? – Priority

The list of primes is an infinite but immutable list so it makes prefect sense to use a precalculated list upto the likely upper bound for the application. Why waste time writing code that may be buggy when there is a correct public list available that can be used to meet the requirements. – Zachar

@Zachar only the OP will be able to tell if using a publicly available list is valid for his purposes. I do know that I would use it in some scenarios, in the same way that I use a publicly available value of pi. – Taxaceous

I've modified my post so that the file is read line by line to avoid loading the whole list into memory. – Kumquat

Well... This answer wasn't what I had in mind when I asked the question :-) I don't mind it, and it's certainly thinking outside the box, but I have a feeling it will never be faster than a decent sieve implementation because by the time primes are sparse enough to be hard to find (see prime number theorem), the numbers will be so long you'll be spending just as much time reading them off the hard drive. – Horsey

@David: I don't see how "sparsity" comes into play when reading to the file. The file only contains the prime numbers, so if you need 70 you just read the first 70 lines and if you need 70,000,000 you just read 70,000,000 lines. It doesn't matter if the numbers stored there are larger or smaller. – Taxaceous

You're right, the sparsity of primes has nothing to do when reading from a text file. What I meant is that the rate at which a method that actually generates primes will be slowed down as primes get larger due to the sparseness of primes (and also the size of the factors). – Horsey

@darin: That memory issue could be discussed. Written in code is not synonymous to loaded in memory. (OTOH, we could just ask #1032927 how he finally store the primes) – Taxaceous

@David: One problem with this question is that if numbers really get that long, it costs lots of time and/or memory to do anything with them. Hence a more realistic problem would be needed. – Taxaceous

Actually, yes, given what starblue and myself said in that efficient storage of primes question, primes can be packed quite efficiently into memory. You can save a file that indicates all the primes up to n in n * 8 / 30 bits by using the file as a bit array where each bit indicates the primality of a number that can be expressed as 30k+/-1,7,11,13... – Horsey

@Daniel, when I said that written in code would consume more memory than if they were read from a file was that you will usually store them into some variable that you will access at runtime. Maybe I am missing your point but could you please give me an example of how you intend storing these list of prime numbers into memory? – Kumquat

I really don't see why my answer got downvoted. While maybe it's not the best answer it seemed to me like a valid solution to the problem. – Kumquat

@darin: I haven't elaborated much, but If I had to do that for production code, I'd try playing with constants saved in a resource file... oops... Maybe I'm missing my own point too :) – Taxaceous

@darin: I myself upvoted it. I made a statement about speed and putting the numbers in the code, but nonetheless this may be not even a valid, but also the best alternative for really accessing a constant list of numbers fast. Also, it's generic and elegant in that the properties of the numbers themselves don't matter much, so it could be reused for Fibonacci numbers or whatever. In a real production world when time is money, this kind of strategies might well make a difference, especially when they don't compromise the clarity of the code at all. – Taxaceous

To improve performance you could have cache - a static list<int> that holds in memory all the primes upto the maximum that has been requested. Thus you only read from slow disk once and then only when absolutely necessary. Thus we have a best case runtime of O(n) (to build the list), dramatically better than the other solutions. – Zachar

Did someone actually check, whether reading primes from a file is faster than generating them with the sieve of Eratosthenes? The sieve runs in time O(n log(log(n))) and all its steps are very simple. Thus it is well possible that computing primes is significantly faster than reading them slowly from a hard disc. – Effusion

@Effusion exactly; and not only is it well possible, but it is also entirely plausible and very likely that the sieve is faster, and in fact I saw it stated several times that it indeed is. Faster. :) :) – Pottle

Answer 11

Using your same algorithm you can do it a bit shorter:

List<int> primes=new List<int>(new int[]{2,3});
for (int n = 5; primes.Count< numberToGenerate; n+=2)
{
  bool isPrime = true;
  foreach (int prime in primes)
  {
    if (n % prime == 0)
    {
      isPrime = false;
      break;
    }
  }
  if (isPrime)
    primes.Add(n);
}

Priority

Answer 12

I know you asked for non-Haskell solution but I am including this here as it relates to the question and also Haskell is beautiful for this type of thing.

module Prime where

primes :: [Integer]
primes = 2:3:primes'
  where
    -- Every prime number other than 2 and 3 must be of the form 6k + 1 or 
    -- 6k + 5. Note we exclude 1 from the candidates and mark the next one as
    -- prime (6*0+5 == 5) to start the recursion.
    1:p:candidates = [6*k+r | k <- [0..], r <- [1,5]]
    primes'        = p : filter isPrime candidates
    isPrime n      = all (not . divides n) $ takeWhile (\p -> p*p <= n) primes'
    divides n p    = n `mod` p == 0

Scientism

Yeah, I'm a big fan of Haskell too (I just wish I knew it better) – Horsey

Answer 13

I wrote a simple Eratosthenes implementation in c# using some LINQ.

Unfortunately LINQ does not provide an infinite sequence of ints so you have to use int.MaxValue:(

I had to cache in an anonimous type the candidate sqrt to avoid to calculate it for each cached prime (looks a bit ugly).

I use a list of previous primes till sqrt of the candidate

cache.TakeWhile(c => c <= candidate.Sqrt)

and check every Int starting from 2 against it

.Any(cachedPrime => candidate.Current % cachedPrime == 0)

Here is the code:

static IEnumerable<int> Primes(int count)
{
    return Primes().Take(count);
}

static IEnumerable<int> Primes()
{
    List<int> cache = new List<int>();

    var primes = Enumerable.Range(2, int.MaxValue - 2).Select(candidate => new 
    {
        Sqrt = (int)Math.Sqrt(candidate), // caching sqrt for performance
        Current = candidate
    }).Where(candidate => !cache.TakeWhile(c => c <= candidate.Sqrt)
            .Any(cachedPrime => candidate.Current % cachedPrime == 0))
            .Select(p => p.Current);

    foreach (var prime in primes)
    {
        cache.Add(prime);
        yield return prime;
    }
}

Another optimization is to avoid checking even numbers and return just 2 before creating the List. This way if the calling method just asks for 1 prime it will avoid all the mess:

static IEnumerable<int> Primes()
{
    yield return 2;
    List<int> cache = new List<int>() { 2 };

    var primes = Enumerable.Range(3, int.MaxValue - 3)
        .Where(candidate => candidate % 2 != 0)
        .Select(candidate => new
    {
        Sqrt = (int)Math.Sqrt(candidate), // caching sqrt for performance
        Current = candidate
    }).Where(candidate => !cache.TakeWhile(c => c <= candidate.Sqrt)
            .Any(cachedPrime => candidate.Current % cachedPrime == 0))
            .Select(p => p.Current);

    foreach (var prime in primes)
    {
        cache.Add(prime);
        yield return prime;
    }
}

Worshipful

I wish I knew LINQ enough to appreciate and understand this answer better :-) Also, I have a feeling that this isn't an implementation of the sieve of Eratosthenes, and that it works conceptually the same as my original function (find the next number that isn't divisible by any of the previously found primes). – Horsey

Yes, but "find the next number that isn't divisible by any of the previously found primes (smaller then number)" is conceptually similar to the sieve of eratosthenes. If you prefer, I can refactor it a bit to make it more readable even if you are not familiar with LINQ. Are you familiar with iterators? – Worshipful

The thing I like of this approach is that the next prime is calculated just when the caller asks for it, so things like "take the first n primes" or "take the primes that are smaller then n" become trivial – Worshipful

Thanks, but I can understand that enough to more or less know what it's doing :-) I like the lazy evaluation, but I still wouldn't call this an implementation of the sieve of Eratosthenes. – Horsey

Answer 14

This is the most elegant I can think of on short notice.

ArrayList generatePrimes(int numberToGenerate)
{
    ArrayList rez = new ArrayList();

    rez.Add(2);
    rez.Add(3);

    for(int i = 5; rez.Count <= numberToGenerate; i+=2)
    {
        bool prime = true;
        for (int j = 2; j < Math.Sqrt(i); j++)
        {
            if (i % j == 0)
            {
                    prime = false;
                    break;
            }
        }
        if (prime) rez.Add(i);
    }

    return rez;
}

Hope this helps to give you an idea. I'm sure this can be optimised, however it should give you an idea how your version could be made more elegant.

EDIT: As noted in the comments this algorithm indeed returns wrong values for numberToGenerate < 2. I just want to point out, that I wasn't trying to post him a great method to generate prime numbers (look at Henri's answer for that), I was mearly pointing out how his method could be made more elegant.

Hulburt

This one returns a wrong result for numberToGenerate < 2 – Cineraria

This is true, however I wasn't designing a algorithm, I was just showing him how his method can be made more elegant. So this version is equally wrong as the one in opening question. – Viper

It didn't occur to me that it was broken for n=1. I changed the question slightly so that the function only has to work for n>1 :-) – Horsey

this admits squares of primes as prime numbers. – Pottle

Answer 15

To make it more elegant, you should refactor out your IsPrime test into a separate method, and handle the looping and increments outside of that.

Legend

Answer 16

I did it in Java using a functional library I wrote, but since my library uses the same concepts as Enumerations, I am sure the code is adaptable:

Iterable<Integer> numbers = new Range(1, 100);
Iterable<Integer> primes = numbers.inject(numbers, new Functions.Injecter<Iterable<Integer>, Integer>()
{
    public Iterable<Integer> call(Iterable<Integer> numbers, final Integer number) throws Exception
    {
        // We don't test for 1 which is implicit
        if ( number <= 1 )
        {
            return numbers;
        }
        // Only keep in numbers those that do not divide by number
        return numbers.reject(new Functions.Predicate1<Integer>()
        {
            public Boolean call(Integer n) throws Exception
            {
                return n > number && n % number == 0;
            }
        });
    }
});

Seiter

Answer 17

Using stream-based programming in Functional Java, I came up with the following. The type Natural is essentially a BigInteger >= 0.

public static Stream<Natural> sieve(final Stream<Natural> xs)
{ return cons(xs.head(), new P1<Stream<Natural>>()
  { public Stream<Natural> _1()
    { return sieve(xs.tail()._1()
                   .filter($(naturalOrd.equal().eq(ZERO))
                           .o(mod.f(xs.head())))); }}); }

public static final Stream<Natural> primes
  = sieve(forever(naturalEnumerator, natural(2).some()));

Now you have a value, that you can carry around, which is an infinite stream of primes. You can do things like this:

// Take the first n primes
Stream<Natural> nprimes = primes.take(n);

// Get the millionth prime
Natural mprime = primes.index(1000000);

// Get all primes less than n
Stream<Natural> pltn = primes.takeWhile(naturalOrd.lessThan(n));

An explanation of the sieve:

1. Assume the first number in the argument stream is prime and put it at the front of the return stream. The rest of the return stream is a computation to be produced only when asked for.
2. If somebody asks for the rest of the stream, call sieve on the rest of the argument stream, filtering out numbers divisible by the first number (the remainder of division is zero).

You need to have the following imports:

import fj.P1;
import static fj.FW.$;
import static fj.data.Enumerator.naturalEnumerator;
import fj.data.Natural;
import static fj.data.Natural.*;
import fj.data.Stream;
import static fj.data.Stream.*;
import static fj.pre.Ord.naturalOrd;

Fleuron

Answer 18

I personally think this is quite a short & clean (Java) implementation:

static ArrayList<Integer> getPrimes(int numPrimes) {
    ArrayList<Integer> primes = new ArrayList<Integer>(numPrimes);
    int n = 2;
    while (primes.size() < numPrimes) {
        while (!isPrime(n)) { n++; }
        primes.add(n);
        n++;
    }
    return primes;
}

static boolean isPrime(int n) {
    if (n < 2) { return false; }
    if (n == 2) { return true; }
    if (n % 2 == 0) { return false; }
    int d = 3;
    while (d * d <= n) {
        if (n % d == 0) { return false; }
        d += 2;
    }
    return true;
}

Calve

Answer 19

Try this LINQ Query, it generates prime numbers as you expected

        var NoOfPrimes= 5;
        var GeneratedPrime = Enumerable.Range(1, int.MaxValue)
          .Where(x =>
            {
                 return (x==1)? false:
                        !Enumerable.Range(1, (int)Math.Sqrt(x))
                        .Any(z => (x % z == 0 && x != z && z != 1));
            }).Select(no => no).TakeWhile((val, idx) => idx <= NoOfPrimes-1).ToList();

Ruwenzori

Answer 20

// Create a test range
IEnumerable<int> range = Enumerable.Range(3, 50 - 3);

// Sequential prime number generator
var primes_ = from n in range
     let w = (int)Math.Sqrt(n)
     where Enumerable.Range(2, w).All((i) => n % i > 0)
     select n;

// Note sequence of output:
// 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47,
foreach (var p in primes_)
    Trace.Write(p + ", ");
Trace.WriteLine("");

Gawky

Answer 21

The simplest method is the trial and error: you try if any number between 2 and n-1 divides your candidate prime n.
First shortcuts are of course a)you only have to check odd numbers, and b)you only hav to check for dividers up to sqrt(n).

In your case, where you generate all previous primes in the process as well, you only have to check if any of the primes in your list, up to sqrt(n), divides n.
Should be the fastest you can get for your money :-)

edit
Ok, code, you asked for it. But I'm warning you :-), this is 5-minutes-quick-and-dirty Delphi code:

procedure TForm1.Button1Click(Sender: TObject);
const
  N = 100;
var
  PrimeList: TList;
  I, J, SqrtP: Integer;
  Divides: Boolean;
begin
  PrimeList := TList.Create;
  for I := 2 to N do begin
    SqrtP := Ceil(Sqrt(I));
    J := 0;
    Divides := False;
    while (not Divides) and (J < PrimeList.Count) 
                        and (Integer(PrimeList[J]) <= SqrtP) do begin
      Divides := ( I mod Integer(PrimeList[J]) = 0 );
      inc(J);
    end;
    if not Divides then
      PrimeList.Add(Pointer(I));
  end;
  // display results
  for I := 0 to PrimeList.Count - 1 do
    ListBox1.Items.Add(IntToStr(Integer(PrimeList[I])));
  PrimeList.Free;
end;

Ottoottoman

And how do you express this in code? :-) – Horsey

Answer 22

Here is a python code example that prints out the sum of all primes below two million:

from math import *

limit = 2000000
sievebound = (limit - 1) / 2
# sieve only odd numbers to save memory
# the ith element corresponds to the odd number 2*i+1
sieve = [False for n in xrange(1, sievebound + 1)]
crosslimit = (int(ceil(sqrt(limit))) - 1) / 2
for i in xrange(1, crosslimit):
    if not sieve[i]:
        # if p == 2*i + 1, then
        #   p**2 == 4*(i**2) + 4*i + 1
        #        == 2*i * (i + 1)
        for j in xrange(2*i * (i + 1), sievebound, 2*i + 1):
            sieve[j] = True
sum = 2
for i in xrange(1, sievebound):
    if not sieve[i]:
        sum = sum + (2*i+1)
print sum

Scientism

Answer 23

I got this by first reading of "Sieve of Atkin" on Wikki plus some prior thought I have given to this - I spend a lot of time coding from scratch and get completely zeroed on folks being critical of my compiler-like, very dense coding style + I have not even done a first attempt to run the code ... many of the paradigm that I have learned to use are here, just read and weep, get what you can.

Be absolutely & totally sure to really test all this before any use, for sure do not show it to anyone - it is for reading and considering the ideas. I need to get primality tool working so this is where I start each time I have to get something working.

Get one clean compile, then start taking away what is defective - I have nearly 108 million keystrokes of useable code doing it this way, ... use what you can.

I will work on my version tomorrow.

package demo;
// This code is a discussion of an opinion in a technical forum.
// It's use as a basis for further work is not prohibited.
import java.util.Arrays;
import java.util.HashSet;
import java.util.ArrayList;
import java.security.GeneralSecurityException;

/**
 * May we start by ignores any numbers divisible by two, three, or five
 * and eliminate from algorithm 3, 5, 7, 11, 13, 17, 19 completely - as
 * these may be done by hand. Then, with some thought we can completely
 * prove to certainty that no number larger than square-root the number
 * can possibly be a candidate prime.
 */

public class PrimeGenerator<T>
{
    //
    Integer HOW_MANY;
    HashSet<Integer>hashSet=new HashSet<Integer>();
    static final java.lang.String LINE_SEPARATOR
       =
       new java.lang.String(java.lang.System.getProperty("line.separator"));//
    //
    PrimeGenerator(Integer howMany) throws GeneralSecurityException
    {
        if(howMany.intValue() < 20)
        {
            throw new GeneralSecurityException("I'm insecure.");
        }
        else
        {
            this.HOW_MANY=howMany;
        }
    }
    // Let us then take from the rich literature readily 
    // available on primes and discount
    // time-wasters to the extent possible, utilizing the modulo operator to obtain some
    // faster operations.
    //
    // Numbers with modulo sixty remainder in these lists are known to be composite.
    //
    final HashSet<Integer> fillArray() throws GeneralSecurityException
    {
        // All numbers with modulo-sixty remainder in this list are not prime.
        int[]list1=new int[]{0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,
        32,34,36,38,40,42,44,46,48,50,52,54,56,58};        //
        for(int nextInt:list1)
        {
            if(hashSet.add(new Integer(nextInt)))
            {
                continue;
            }
            else
            {
                throw new GeneralSecurityException("list1");//
            }
        }
        // All numbers with modulo-sixty remainder in this list are  are
        // divisible by three and not prime.
        int[]list2=new int[]{3,9,15,21,27,33,39,45,51,57};
        //
        for(int nextInt:list2)
        {
            if(hashSet.add(new Integer(nextInt)))
            {
                continue;
            }
            else
            {
                throw new GeneralSecurityException("list2");//
            }
        }
        // All numbers with modulo-sixty remainder in this list are
        // divisible by five and not prime. not prime.
        int[]list3=new int[]{5,25,35,55};
        //
        for(int nextInt:list3)
        {
            if(hashSet.add(new Integer(nextInt)))
            {
                continue;
            }
            else
            {
                throw new GeneralSecurityException("list3");//
            }
        }
        // All numbers with modulo-sixty remainder in
        // this list have a modulo-four remainder of 1.
        // What that means, I have neither clue nor guess - I got all this from
        int[]list4=new int[]{1,13,17,29,37,41,49,53};
        //
        for(int nextInt:list4)
        {
            if(hashSet.add(new Integer(nextInt)))
            {
                continue;
            }
            else
            {
                throw new GeneralSecurityException("list4");//
            }
        }
        Integer lowerBound=new Integer(19);// duh
        Double upperStartingPoint=new Double(Math.ceil(Math.sqrt(Integer.MAX_VALUE)));//
        int upperBound=upperStartingPoint.intValue();//
        HashSet<Integer> resultSet=new HashSet<Integer>();
        // use a loop.
        do
        {
            // One of those one liners, whole program here:
            int aModulo=upperBound % 60;
            if(this.hashSet.contains(new Integer(aModulo)))
            {
                continue;
            }
            else
            {
                resultSet.add(new Integer(aModulo));//
            }
        }
        while(--upperBound > 20);
        // this as an operator here is useful later in your work.
        return resultSet;
    }
    // Test harness ....
    public static void main(java.lang.String[] args)
    {
        return;
    }
}
//eof

Johm

Answer 24

To find out first 100 prime numbers, Following java code can be considered.

int num = 2;
int i, count;
int nPrimeCount = 0;
int primeCount = 0;

    do
    {

        for (i = 2; i <num; i++)
        {

             int n = num % i;

             if (n == 0) {

             nPrimeCount++;
         //  System.out.println(nPrimeCount + " " + "Non-Prime Number is: " + num);

             num++;
             break;

             }
       }

                if (i == num) {

                    primeCount++;

                    System.out.println(primeCount + " " + "Prime number is: " + num);
                    num++;
                }


     }while (primeCount<100);

Takamatsu

Answer 25

Try this code.

protected bool isPrimeNubmer(int n)
    {
        if (n % 2 == 0)
            return false;
        else
        {
            int j = 3;
            int k = (n + 1) / 2 ;

            while (j <= k)
            {
                if (n % j == 0)
                    return false;
                j = j + 2;
            }
            return true;
        }
    }
    protected void btn_primeNumbers_Click(object sender, EventArgs e)
    {
        string time = "";
        lbl_message.Text = string.Empty;
        int num;

        StringBuilder builder = new StringBuilder();

        builder.Append("<table><tr>");
        if (int.TryParse(tb_number.Text, out num))
        {
            if (num < 0)
                lbl_message.Text = "Please enter a number greater than or equal to 0.";
            else
            {
                int count = 1;
                int number = 0;
                int cols = 11;

                var watch = Stopwatch.StartNew();

                while (count <= num)
                {
                    if (isPrimeNubmer(number))
                    {
                        if (cols > 0)
                        {
                            builder.Append("<td>" + count + " - " + number + "</td>");
                        }
                        else
                        {
                            builder.Append("</tr><tr><td>" + count + " - " + number + "</td>");
                            cols = 11;
                        }
                        count++;
                        number++;
                        cols--;
                    }
                    else
                        number++;
                }
                builder.Append("</table>");
                watch.Stop();
                var elapsedms = watch.ElapsedMilliseconds;
                double seconds = elapsedms / 1000;
                time = seconds.ToString();
                lbl_message.Text = builder.ToString();
                lbl_time.Text = time;
            }
        }
        else
            lbl_message.Text = "Please enter a numberic number.";

        lbl_time.Text = time;

        tb_number.Text = "";
        tb_number.Focus();
    }

Here is the aspx code.

<form id="form1" runat="server">
    <div>
        <p>Please enter a number: <asp:TextBox ID="tb_number" runat="server"></asp:TextBox></p>

        <p><asp:Button ID="btn_primeNumbers" runat="server" Text="Show Prime Numbers" OnClick="btn_primeNumbers_Click" />
        </p>
        <p><asp:Label ID="lbl_time" runat="server"></asp:Label></p>
        <p><asp:Label ID="lbl_message" runat="server"></asp:Label></p>
    </div>
</form>

Results: 10000 Prime Numbers in less than one second

100000 Prime Numbers in 63 seconds

Screenshot of first 100 Prime Numbers

Bequest

Trying it, I could gauge its effectiveness and presentation of resutls: please argue its elegance. – Sandry

The styling of result is just an added part. Let me discuss the algorithm for return true/false as prime number. n%2 will eliminate half of the numbers because even number are always divisible by 2. In else code, I am dividing by odd numbers only, increasing divisible by two (so next divisible is also odd) upto half of that number which is prime or not. Why half, to not waste time because it will give us answer in fraction. – Bequest

log10(63)~=1.8, i.e. your data shows growth rate of n^1.8. This is very slow; optimal sieve of Eratosthenes implementations exibit ~ n^1.01..1.05; optimal trial division ~ n^1.35..1.45. Your isPrimeNubmer indeed implement the suboptimal tril division; its asymptotycs will worsen to about n^2 (or even above it) when you try to generate even more primes. – Pottle