90

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).

5
  • 1
    it would be better in order to me retutning ienumerable<int> and yielding one by one Jul 6, 2012 at 16:22
  • 4
    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? Aug 20, 2013 at 22:36
  • 1
    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.
    – Will Ness
    Aug 22, 2013 at 14:21
  • 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.
    – Will Ness
    Aug 25, 2015 at 10:51
  • What kind of prime numbers are you looking for? What tests should they pass?
    – jww
    Mar 26, 2018 at 2:27

25 Answers 25

51

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;
}
9
  • 3
    That's a very nice implementation of the sieve of Eratosthenes Jun 25, 2009 at 10:55
  • 1
    shoultn't it be enough to loop while i <= Math.sqrt(limit) in the outer loop?
    – Christoph
    Jun 26, 2009 at 8:04
  • 1
    @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.
    – starblue
    Jul 4, 2009 at 9:07
  • 1
    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 Aug 16, 2010 at 14:24
  • 5
    By replacing BitSet by a class implementing wheel factorization for 2, 3 and 5 it becomes almost 3 times faster.
    – starblue
    Oct 26, 2010 at 14:15
42

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;
}
2
  • 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. Dec 28, 2011 at 20:48
  • 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.
    – KnD
    Feb 10, 2015 at 4:48
31

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();
}
3
  • 2
    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! May 5, 2020 at 22:23
  • shorter code does not mean better. If that were true, we'd all be writing Perl.
    – gbjbaanb
    Oct 25, 2022 at 17:27
  • 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.
    – Kirkaiya
    Mar 20 at 23:22
10

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;
}
3
  • 1
    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)
    – yairchu
    Jun 26, 2009 at 9:03
  • Why using the square root? What's the mathematical background for such option? I, probably dully, would only divide by 2. Jun 26, 2009 at 13:44
  • 3
    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. Jun 27, 2009 at 4:15
9

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);
    }
}
1
  • 2
    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.
    – Brian
    Dec 7, 2010 at 15:06
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.

5

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)
4

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.

1
  • 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.
    – Dave Black
    Mar 5, 2013 at 20:32
4

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
    }
1
  • i'd do that with a bool instead of enum...
    – Letterman
    Oct 28, 2009 at 16:36
3

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

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
1
  • Yeah, I'm a big fan of Haskell too (I just wish I knew it better) Jun 25, 2009 at 10:28
3

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.

23
  • 3
    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. Jun 25, 2009 at 10:03
  • 15
    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
    – stevenvh
    Jun 25, 2009 at 10:09
  • 8
    It would be faster if you actually wrote the prime numbers in the source code itself, instead of reading them from a file. Jun 25, 2009 at 10:15
  • 3
    Consume much memory? more than reading the full primes list as text into... memory? Do you know how strings work in .net?
    – jmservera
    Jun 25, 2009 at 10:37
  • 6
    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.
    – AndyM
    Jun 25, 2009 at 10:45
3

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;
    }
}
4
  • 1
    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). Jun 25, 2009 at 13:02
  • 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?
    – Maghis
    Jun 25, 2009 at 13:22
  • 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
    – Maghis
    Jun 25, 2009 at 13:25
  • 1
    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. Jun 26, 2009 at 1:29
1

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.

1

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

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.

4
  • 3
    This one returns a wrong result for numberToGenerate < 2
    – Peter Smit
    Jun 25, 2009 at 10:01
  • 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. Jun 25, 2009 at 10:27
  • 1
    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 :-) Jun 25, 2009 at 10:39
  • this admits squares of primes as prime numbers.
    – Will Ness
    Feb 3, 2013 at 18:09
1

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

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

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();
1
// 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("");
0

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
0

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;
1
  • 1
    And how do you express this in code? :-) Jun 25, 2009 at 10:43
0

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);
0
0

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
0

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 enter image description here

3
  • 1
    Trying it, I could gauge its effectiveness and presentation of resutls: please argue its elegance.
    – greybeard
    May 26, 2015 at 16:45
  • 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.
    – riz
    May 27, 2015 at 17:25
  • 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.
    – Will Ness
    Aug 25, 2015 at 10:26

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