to calculate one million prime numbers

Question

I have got one question to print one million prime numbers . I have written a java program for that .. It's currently taking 1.5 mins approx to calculate it .. I think my solution is not that efficient. I have used the below algo:

• Adding 1 2 3 to the prime list initially
• Calculating the last digit of the number to be checked
• Checking if the digit is 0 , 2 or 4 or 6 or 8 then skipping the number
• else calculating the square root of the number ..
• Trying to Divide the number starting from 2 till the square root of the number
• if number is divisible then skipping the number else adding it to the prime list

I have read several other solutions as well , but I didn't find a good answer. Please suggest ideally what should be approx minimum time to calculate this and what changes are required to make the algorithm more efficient.

Answer 1

If you added 1 to your list, your answer is wrong already :)

Anyway, Sieve of Erathosthenes is where you should begin, it's incredibly simple and quite efficient.

Once you're familiar with the idea of sieves and how they work, you can move on to Sieve of Atkin, which is a bit more complicated but obviously more efficient.

Answer 2

Key things:

1. Skip all even numbers. Start with 5, and just add two at a time.
2. 1 isn't a prime number...
3. Test a number by finding the mod of all prime numbers till the square root of the number. No need to test anything but primes.

Answer 3

A simple sieve of Eratosthenes runs like the clappers. This calculates the 1,000,000th prime in less than a second on my box:

class PrimeSieve
{
    public List<int> Primes;

    private BitArray Sieve;

    public PrimeSieve(int max)
    {
        Primes = new List<int> { 2, 3 }; // Must include at least 2, 3.
        Sieve = new BitArray(max + 1);
        foreach (var p in Primes)
            for (var i = p * p; i < Sieve.Length; i += p) Sieve[i] = true;
    }

    public int Extend()
    {
        var p = Primes.Last() + 2; // Skip the even numbers.
        while (Sieve[p]) p += 2;
        for (var i = p * p; i < Sieve.Length; i += p) Sieve[i] = true;
        Primes.Add(p);
        return p;
    }
}

EDIT: sieving optimally starts from p^2, not 2p, as Will Ness correctly points out (all compound numbers below p^2 will have been marked in earlier iterations).