Most elegant way to generate prime numbers

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

Answer 1

Look at:

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Answer 2

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.

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

Answer 4

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.

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

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;

Answer 10

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

Answer 11

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

Answer 12

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

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

Answer 14

You might be interested in the Sieve of Atkin.

It is an optimized version of the sieve of Eratosthene.

Answer 15

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.

Answer 16

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;

Answer 17

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

Answer 18

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 *n*th 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;
}

Answer 19

Use Wolfram|Alpha ;)

http://www.wolframalpha.com/input/?i=first+10+prime+numbers

Answer 20

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

Answer 21

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
    }

Answer 22

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(2, (int)Math.Sqrt(i)).All(j => i % j != 0)
            select i;
    return r.ToList();
}

Answer 23

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

Cheers

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