[Tapas Bose]

Ferencn, on 01 March 2010 - 03:17 AM, said:

Sorry again. I must be getting old :-)
i misread 4*x*x+y*y as 4 (x*x+y*y) and obviously that is wrong...

I change it as you say. The output is :
[email protected]:~/Prime Number Program/Atkin$ g++ Atkin.cpp -o Atkin.o
[email protected]:~/Prime Number Program/Atkin$ ./Atkin.o

Number of Prime : 664579
Execution time : 1293 ms.

Which is the original value of number of prime below 10,000,000. Sir can you please explain the bit shift operation you have done.

[Ferencn]

Martyn.Rae, on 01 March 2010 - 11:14 AM, said:

Your SieveOfEratosthenes is incorrect. Here is the corrected code

class SieveOfEratosthenes 
{ 
    private : 
        ulong Limit; 
        static bool *IsPrime; 
         
    public : 
        SieveOfEratosthenes() { } 
        SieveOfEratosthenes(ulong Limit) : Limit(Limit) 
        {                        
            try 
            { 
                IsPrime = new bool[Limit + 1];
	        for (ulong i = 2; i*i <= Limit; i++) IsPrime[i] = true;
            } 

I think that line *should* read:

    for (ulong i = 0; <= Limit; i++) IsPrime[i] = true;

EDIT: changed false to true in above line of code.
Otherwise all IsPrime[] for i > sqrt(Limit) will not be initialized correctly.

This post has been edited by Ferencn: 01 March 2010 - 04:51 AM

[Ferencn]

Tapas Bose, on 01 March 2010 - 11:45 AM, said:

Ferencn, on 01 March 2010 - 03:17 AM, said:

Sorry again. I must be getting old :-)
i misread 4*x*x+y*y as 4 (x*x+y*y) and obviously that is wrong...

I change it as you say. The output is :
[email protected]:~/Prime Number Program/Atkin$ g++ Atkin.cpp -o Atkin.o
[email protected]:~/Prime Number Program/Atkin$ ./Atkin.o

Number of Prime : 664579
Execution time : 1293 ms.

Which is the original value of number of prime below 10,000,000. Sir can you please explain the bit shift operation you have done.

No problem, but before I start: are you familiar with binary notation? if so, I can explain quickly, if not I may have to be more elaborate.

This post has been edited by Ferencn: 01 March 2010 - 04:54 AM

[Tapas Bose]

Martyn.Rae, on 01 March 2010 - 03:41 AM, said:

You are correct in saying that static variables are initialized to zero. Unfortunately, you are using a static pointer to an array. This will be set to zero, but then you allocate the array using the new operator. This provides you with a chunk of memory that contains well, garbage!

If you use the same initialization code for both prime number classes, it will not make any difference to the overall timings.

Thank you sir, I understand your point. Can you please tell me if I write

class SieveOfAtkin
{
    private :
            static bool IsPrime[100000];
}

Then outside the class how can I re-declare IsPrime?
Another point I want to tell you, if I print the IsPrime array declared as my first post without doing any prime generation then it print all 0 no garbage value, what is the reason behind this behavior sir?

[Martyn.Rae]

Ferencn, on 01 March 2010 - 10:48 AM, said:

Martyn.Rae, on 01 March 2010 - 11:14 AM, said:

Your SieveOfEratosthenes is incorrect. Here is the corrected code

class SieveOfEratosthenes 
{ 
    private : 
        ulong Limit; 
        static bool *IsPrime; 
         
    public : 
        SieveOfEratosthenes() { } 
        SieveOfEratosthenes(ulong Limit) : Limit(Limit) 
        {                        
            try 
            { 
                IsPrime = new bool[Limit + 1];
	        for (ulong i = 2; i*i <= Limit; i++) IsPrime[i] = true;
            } 

I think that line *should* read:

    for (ulong i = 0; <= Limit; i++) IsPrime[i] = false;

Otherwise all IsPrime[] for i > sqrt(Limit) will not be initialized correctly.

For the SieveOfEratosthenes class, the code is correct. I haven't checked that code for the other class. The assumption is that we are running through all numbers that we have not ascertained are not primes already. So starting off, all numbers are set to prime. Starting with 2, we run through every single number in the array, setting those whose modulo 2 is zero, to false i.e. they are not primes. The next number we consider is 3, so we go through all entries in the array whose cell entry is true, to determine if they are also 3 modulo zero. etc etc.
Those numbers left in the array that are true as in IsPrime[n] = true are truely prime numbers. BTW: Yes j += i is better optimization. I hadn't bothered to optimize the code I had written as I was more concerned about getting Tapas Bose to understand that what had been posted for that class was incorrect.

[Tapas Bose]

Ferencn, on 01 March 2010 - 03:54 AM, said:

No problem, but before I start: are you familiar with binary notation? if so, I can explain quickly, if not I may have to be more elaborate.

Yes sir I am familiar with binary notation. eg:
(2)₁₀=(10)₂.

[Ferencn]

Martyn.Rae, on 01 March 2010 - 11:57 AM, said:

Ferencn, on 01 March 2010 - 10:48 AM, said:

Martyn.Rae, on 01 March 2010 - 11:14 AM, said:

Your SieveOfEratosthenes is incorrect. Here is the corrected code

class SieveOfEratosthenes 
{ 
    private : 
        ulong Limit; 
        static bool *IsPrime; 
         
    public : 
        SieveOfEratosthenes() { } 
        SieveOfEratosthenes(ulong Limit) : Limit(Limit) 
        {                        
            try 
            { 
                IsPrime = new bool[Limit + 1];
	        for (ulong i = 2; i*i <= Limit; i++) IsPrime[i] = true;
            } 

I think that line *should* read:

    for (ulong i = 0; <= Limit; i++) IsPrime[i] = true;

Otherwise all IsPrime[] for i > sqrt(Limit) will not be initialized correctly.

For the SieveOfEratosthenes class, the code is correct. I haven't checked that code for the other class. The assumption is that we are running through all numbers that we have not ascertained are not primes already. So starting off, all numbers are set to prime. Starting with 2, we run through every single number in the array, setting those whose modulo 2 is zero, to false i.e. they are not primes. The next number we consider is 3, so we go through all entries in the array whose cell entry is true, to determine if they are also 3 modulo zero. etc etc.
Those numbers left in the array that are true as in IsPrime[n] = true are truely prime numbers. BTW: Yes j += i is better optimization. I hadn't bothered to optimize the code I had written as I was more concerned about getting Tapas Bose to understand that what had been posted for that class was incorrect.

Note my correction, I accidentally typed 'false' instead of true in the codeline.
Correct me if I am wrong, but there are certainly numbers larger than the square root of 10.000.000 that are a prime...
Shouldn't those be initialized as a candidate (true, until proven wrong) ?
This loop is part of the constructor code that initializes the table, not the code that eliminates candidates.

[Ferencn]

Tapas Bose, on 01 March 2010 - 12:02 PM, said:

Ferencn, on 01 March 2010 - 03:54 AM, said:

No problem, but before I start: are you familiar with binary notation? if so, I can explain quickly, if not I may have to be more elaborate.

Yes sir I am familiar with binary notation. eg:
(2)₁₀=(10)₂.

In that case, a left-shift by one bit (or adding a zero on the right!!) of an integer will result in a multiplication by 2:

0110 (6)
0110 << 1 --> 1100 = 12

shifting 2 bits to the left is multiplying by 4, 3 by 8 etc.

Just like in decimal: adding a zero at the end is multiplying by 10, 2 zeroes by 100 etc.

I use the shift in this case to eliminate a multiplication. Modern processors don't benefit as much as old processors used to do, but it may help...

Other optimizations i did was:
premultiply the squares, so we don't have to do that again.
And then I observed that:

3*x*x+y*y == 4*x*x+y*y - x*x, and
3*x*x-y*y == 3*x*x+y*y - y*y - y*y == 3*x*x+y*y - 2(y*y)

I just noticed another thing:

        // moving this out of the inner loop saves some calculations
        ulong xsquared = x*x;
        for (ulong y = 1; y <= SqrtLimit; y++)
        {
            ulong ysquared = y*y;

            ulong n = (xsquared<<2)+ysquared;

            // only need one check for n<= Limit!
            // We will be only subtracting from n, so once past
            // this test, it will always pass

            if (n<=Limit)
            {
                if ((n % 12 == 1) || (n % 12 == 5))
                {
                    IsPrime[n] ^= true;
                }

                n -= xsquared;
                if (n % 12 == 7)
                {
                    IsPrime[n] ^= true;
                }

                if (x>y)
                {
                    // ONLY DO calculation WHEN X>Y!!
                    n -= (ysquared<<1);
                    if (n % 12 == 11)
                    {
                        IsPrime[n] ^= true;
                    }
                }
            }

This post has been edited by Ferencn: 01 March 2010 - 05:25 AM

[Tapas Bose]

Ferencn, on 01 March 2010 - 04:14 AM, said:

Tapas Bose, on 01 March 2010 - 12:02 PM, said:

Ferencn, on 01 March 2010 - 03:54 AM, said:

No problem, but before I start: are you familiar with binary notation? if so, I can explain quickly, if not I may have to be more elaborate.

Yes sir I am familiar with binary notation. eg:
(2)₁₀=(10)₂.

In that case, a left-shift by one bit (or adding a zero on the right!!) of an integer will result in a multiplication by 2:

0110 (6)
0110 << 1 --> 1100 = 12

shifting 2 bits to the left is multiplying by 4, 3 by 8 etc.

Just like in decimal: adding a zero at the end is multiplying by 10, 2 zeroes by 100 etc.

I use the shift in this case to eliminate a multiplication. Modern processors don't benefit as much as old processors used to do, but it may help...

Other optimizations i did was:
premultiply the squares, so we don't have to do that again.
And then I observed that:

3*x*x+y*y == 4*x*x+y*y - x*x, and
3*x*x-y*y == 3*x*x+y*y - y*y - y*y == 3*x*x+y*y - 2(y*y)

I just noticed another thing:

        // moving this out of the inner loop saves some calculations
        ulong xsquared = x*x;
        for (ulong y = 1; y <= SqrtLimit; y++)
        {
            ulong ysquared = y*y;

            ulong n = (xsquared<<2)+ysquared;

            // only need one check for n<= Limit!
            // We will be only subtracting from n, so once past
            // this test, it will always pass

            if (n<=Limit)
            {
                if ((n % 12 == 1) || (n % 12 == 5))
                {
                    IsPrime[n] ^= true;
                }

                n -= xsquared;
                if (n % 12 == 7)
                {
                    IsPrime[n] ^= true;
                }

                if (x>y)
                {
                    // ONLY DO calculation WHEN X>Y!!
                    n -= (ysquared<<1);
                    if (n % 12 == 11)
                    {
                        IsPrime[n] ^= true;
                    }
                }
            }

Thank you very much sir. Bit shift operation is now clear to me.

[Tapas Bose]

After getting lots of information from here this is my modified implementation :
Sieve of Atkin:

#include <new>
#include <cmath>
#include <iostream>
#include <exception>
#include <sys/time.h>

typedef unsigned long long ulong;

using namespace std;

class SieveOfAtkin
{
	private :
		ulong Limit;
		static bool *IsPrime;
		
	public :
		SieveOfAtkin() { }
		SieveOfAtkin(ulong Limit) : Limit(Limit)
		{			
			try
			{
				IsPrime = new bool[Limit];
				
				for (ulong i = 0; i <= Limit; i++)
				{
					IsPrime[i] = false;
				}
			}
			catch(bad_alloc&)
			{
				cerr << "  Memory allocation unsuccessful." << endl;
			}
		}
		
		static long NoOfPrime;
		
		void PrimeGen();
		void Display();
		
};

bool *SieveOfAtkin :: IsPrime;
long SieveOfAtkin :: NoOfPrime = 0;

void SieveOfAtkin :: PrimeGen()
{
	ulong SqrtLimit = (ulong)ceil(sqrt((double)Limit));
	
	for (ulong x = 1; x <= SqrtLimit; x++)

        {
        	for (ulong y = 1; y <= SqrtLimit; y++)
        	{
        		ulong xsquared = x*x;
            		ulong ysquared = y*y;

            		ulong n = (xsquared << 2) + ysquared; // n = 4*x*x + y*y

            		if (n <= Limit && (n % 12 == 1 || n % 12 == 5))
            		{
                		IsPrime[n] ^= true;
            		}

            		n -= xsquared;  // n = 3*x*x + y*y
            
            		if (n <= Limit && n % 12 == 7)
            		{
                		IsPrime[n] ^= true;
            		}

            		if (x > y)
            		{
                		n -= (ysquared << 1);  // n = 3*x*x - y*y
                		
                		if (n <= Limit && n % 12 == 11)
                		{
                    			IsPrime[n] ^= true;
                		}
            		}

            	}

        }
        
        for (ulong n = 5; n <= SqrtLimit; n++)

        {

		if (IsPrime[n])

            	{

                	ulong s = n * n;



                	for (ulong k = s; k <= Limit; k += s)

                	{

                    		IsPrime[k] = false;

                	}

            	}

        }
        
        IsPrime[2] = true;
        IsPrime[3] = true;
}

void SieveOfAtkin :: Display()
{	
	int Counter = 0;
	
	for (ulong i = 2; i <= Limit; i++)
	{
		if (IsPrime[i])
		{
			/*cout << i << "\t";
			
			Counter++;
		
			if (Counter == 19)
			{
				cout << endl;
				Counter = 0;
			}*/
			
			NoOfPrime++;
		}
	}
	
	cout << endl << endl;
}

unsigned GetTickCount()
{
        struct timeval tv;
        
        if (gettimeofday(&tv, NULL) != 0)
        {
                return 0;
        }

        return (tv.tv_sec * 1000) + (tv.tv_usec / 1000);
}

int main ()
{
	unsigned StartTime = GetTickCount();
	
	SieveOfAtkin Object = SieveOfAtkin(10000000LLU);
	
	Object.PrimeGen();
	
	Object.Display();

	cout << "  Number of Prime : " << Object.NoOfPrime << endl;
	cout << "  Execution time : " << (GetTickCount() - StartTime) << " ms." << endl << endl;
	
	return 0;
}

Output :
Number of Prime : 664579
Execution time : 1094 ms.

Sieve of Eratosthenes :

#include <new>
#include <cmath>
#include <iostream>
#include <exception>
#include <sys/time.h>

typedef unsigned long long ulong;

using namespace std;

class SieveOfEratosthenes
{
	private :
		ulong Limit;
		static bool *IsPrime;
	
	public :
		SieveOfEratosthenes() { }
		SieveOfEratosthenes(ulong Limit) : Limit(Limit)
		{			
			try
			{
				IsPrime = new bool[Limit + 1];
				
				for (ulong i = 0; i <= Limit; i++)
				{
					IsPrime[i] = true;
				}
			}
			catch(bad_alloc&)
			{
				cerr << "  Memory allocation unsuccessful." << endl;
			}
		}
		
		static long NoOfPrime;
		
		void PrimeGen();
		void Display();
};

bool *SieveOfEratosthenes :: IsPrime;
long SieveOfEratosthenes :: NoOfPrime = 0;

void SieveOfEratosthenes :: PrimeGen()
{
	for (ulong i = 2; i*i <= Limit; i++) 
        {
        	if (IsPrime[i]) 
            	{
                	for (ulong j = i * 2; j <= Limit; j += i) 
            		{
                		IsPrime[j] = false; 
            		} 
            	}
        }
}

void SieveOfEratosthenes :: Display()
{
	int Counter = 0;
	
	for (ulong i = 2; i <= Limit; i++)
	{
		if (IsPrime[i])
		{
			/*cout << i << "\t";
			
			Counter++;
		
			if (Counter == 19)
			{
				cout << endl;
				Counter = 0;
			}*/
			
			NoOfPrime++;
		}
	}
	
	cout << endl << endl;
}

unsigned GetTickCount()
{
        struct timeval tv;
        
        if (gettimeofday(&tv, NULL) != 0)
        {
                return 0;
        }

        return (tv.tv_sec * 1000) + (tv.tv_usec / 1000);
}

int main ()
{
	unsigned StartTime = GetTickCount();
	
	SieveOfEratosthenes Object = SieveOfEratosthenes(10000000LLU);
	
	Object.PrimeGen();
	
	Object.Display();

	cout << "  Number of Prime : " << Object.NoOfPrime << endl;
	cout << "  Execution time : " << (GetTickCount() - StartTime) << " ms." << endl << endl;
	
	return 0;
}

Output :
Number of Prime : 664579
Execution time : 1268 ms.

Thanks to Martyn.Rae and Ferencn.

[baavgai]

PlasticineGuy, on 01 March 2010 - 04:37 AM, said:

Why are you using a class? In my opinion classes should not be used when you do not need operator overloading or more than one instace of something.

I'd disagree. In fact, this lends itself to classes. Just not as the OP is doing.

In the classes, static is nonsensical. Don't use static unless you understand the point of it. You clearly don't. Also, as Martyn pointed out, the Eratosthenes implementation is simply wrong. I don't like Martyn's either, but it's technically correct. Eratosthenes offers an idea, not source code. It's up to the programmer to be smart about it.

Do this test with a base class and implementations of the algorithms. Since both use a boolean blotter, we can use that.

Here's my code, and my implementation:

#include <new>
#include <cmath>
#include <iostream>
#include <exception>
#include <sys/time.h>

using namespace std;

class PrimeSieve {
protected:
	const ulong limit;
	bool *isPrime;

	void fill(bool v) { for (ulong i = 2; i <= limit; i++) { isPrime[i] = v; } }
public :
	PrimeSieve(ulong n, bool fillValue) : limit(n) {
		isPrime = new bool[limit+1];
		fill(fillValue);
	}
	~PrimeSieve() { delete [] isPrime; }
	long getNumberOfPrimes() const;
	virtual void PrimeGen() = 0;
	virtual const char *getName() const = 0;
};


long PrimeSieve::getNumberOfPrimes() const {
	long numberOfPrimes = 0;
	
	for (ulong i = 2; i < limit; i++) {
		if (isPrime[i]) { numberOfPrimes++; }
	}
	return numberOfPrimes;
}


class SieveOfAtkin : public PrimeSieve {
	public :
		SieveOfAtkin(ulong n) : PrimeSieve(n, false) { }
		const char *getName() const { return "SieveOfAtkin"; }
		void PrimeGen();
};

void SieveOfAtkin :: PrimeGen() {
	ulong SqrtLimit = (ulong)ceil(sqrt((double)limit));
	
	for (ulong x = 1; x <= SqrtLimit; x++) {
		for (ulong y = 1; y <= SqrtLimit; y++) {
			ulong n = 4 * x * x + y * y;
			if (n <= limit && (n % 12 == 1 || n % 12 == 5)) {
				isPrime[n] ^= true;
			}
			n = 3 * x * x + y * y;
			if (n <= limit && n % 12 == 7) { isPrime[n] ^= true; }
			n = 3 * x * x - y * y;
			if (x > y && n <= limit && n % 12 == 11) { isPrime[n] ^= true; }
		}
	}
	for (ulong n = 5; n <= SqrtLimit; n++) {
		if (isPrime[n]) {
			ulong s = n * n;
			for (ulong k = s; k <= limit; k += s) { isPrime[k] = false; }
		}

	}
	isPrime[2] = true;
	isPrime[3] = true;
}



class SieveOfEratosthenes : public PrimeSieve {
public :
	SieveOfEratosthenes(ulong n) : PrimeSieve(n, true) { }
	const char *getName() const { return "SieveOfEratosthenes"; }
	void PrimeGen() {
		for (ulong i = 2; i*i <= limit; i++) {
			if (!isPrime[i]) {
				for (ulong j = i; i*j < limit; j++) { isPrime[i*j] = true; }
			}
		}
	}
		
};

class SieveOfEratosthenesMartyn : public PrimeSieve {
public :
	SieveOfEratosthenesMartyn(ulong n) :  PrimeSieve(n, true) { }
	const char *getName() const { return "SieveOfEratosthenesMartyn"; }
	void PrimeGen() {
		for (ulong i = 2; i*i <= limit; i++) { 
			if (isPrime[i])  { 
				for (ulong j = i+1; j <= limit; j++) {
					if ( j%i == 0 ) { isPrime[j] = false;  }
				} 
			} 
		} 
	}
		
};

class SieveOfEratosthenesBaavgai : public PrimeSieve {
public :
	SieveOfEratosthenesBaavgai(ulong n) :  PrimeSieve(n, true) { }
	const char *getName() const { return "SieveOfEratosthenesBaavgai"; }
	void PrimeGen() {
		for (ulong i = 2; i*i <= limit; i++) { 
			if (isPrime[i])  { 
				for (ulong j = i+i; j <= limit; j += i) { isPrime[j] = false; } 
			} 
		} 
	}
		
};
	


unsigned GetTickCount() {
	struct timeval tv;

	if (gettimeofday(&tv, NULL) != 0) {  return 0; }
	return (tv.tv_sec * 1000) + (tv.tv_usec / 1000);
}


void testSieve(PrimeSieve &sieve) {
	cout << "Testing: " << sieve.getName() << endl;
	unsigned startTime = GetTickCount();
	sieve.PrimeGen();
	unsigned endTime = GetTickCount();
	// sieve.Display();
	cout << "  Number of Prime : " << sieve.getNumberOfPrimes() << endl;
	cout << "  Execution time : " << (endTime - startTime) << " ms." << endl << endl;
}

#define testClass(className) ps = new className(testSize); testSieve(*ps); delete ps;

int main () {
	ulong testSize = 10000000LLU;
	//ulong testSize = 100;
	PrimeSieve *ps;
	testClass(SieveOfAtkin);
	testClass(SieveOfEratosthenes);
	testClass(SieveOfEratosthenesMartyn);
	testClass(SieveOfEratosthenesBaavgai);
	
	return 0;
}

And the results:

Testing: SieveOfAtkin
  Number of Prime : 664579
  Execution time : 1198 ms.

Testing: SieveOfEratosthenes
  Number of Prime : 9999998
  Execution time : 0 ms.

Testing: SieveOfEratosthenesMartyn
  Number of Prime : 664579
  Execution time : 150769 ms.

Testing: SieveOfEratosthenesBaavgai
  Number of Prime : 664579
  Execution time : 326 ms.

I'm afraid I beat Atkin using only an intelligent Eratosthenes. In computers, implementation is everything.

This post has been edited by baavgai: 01 March 2010 - 06:40 AM

[Tapas Bose]

@ baavgai. Thank you sir. Actually I thought that declaring IsPrime as static I can fill it with 0. Sir is there any way of better implementation of Sieve of Atkin?

[Martyn.Rae]

[quote name='baavgai' date='01 March 2010 - 12:40 PM' timestamp='1267450804' post='943012']

PlasticineGuy, on 01 March 2010 - 04:37 AM, said:

... Also, as Martyn pointed out, the Eratosthenes implementation is simply wrong. I don't like Martyn's either, but it's technically correct.

I would just like to point out that it ws not my solution ... I merely corrected what was wrong with the code

[Ferencn]

@ baavgai: Atkin was beaten by Eratosthenes from the beginning!
Martyn and I already found the improvements that you propose for Eratosthenes...

Let me share with you what I optimized in Atkin: (I did not rethink the algorithm, I just took the code provided by the OP and tweaked it a bit)

What it boils down to is that I basically eliminated all (unecessary) multiplications.

void SieveOfAtkin :: PrimeGen() {
        ulong SqrtLimit = (ulong)ceil(sqrt((double)limit));
        
        ulong xsquared = 1;
        ulong xadd = 3;
        for (ulong x = 1; x <= SqrtLimit; x++) {
                ulong ysquared = 1;
                ulong yadd = 3;
                for (ulong y = 1; y <= SqrtLimit; y++) {

                        ulong n = (xsquared<<2) + ysquared;

                        if (n <= limit && (n % 12 == 1 || n % 12 == 5)) {
                                isPrime[n] ^= true;
                        }
                        n -= xsquared;
                        if (n <= limit && n % 12 == 7) { isPrime[n] ^= true; }
                        if (x > y)
                        {
                            n -=  ysquared<<1;
                            if (n <= limit && n % 12 == 11) { isPrime[n] ^= true; }
                        }
                        ysquared+=yadd;
                        yadd+=2;
                }
                xsquared+=xadd; // usu=ing the fact that difference between 1*1 and 2*2 == 3, 2*2 and 3*3 == 5 etc
                xadd+=2;        // increase the stepsize
        }
        // no need to test even candidates so increment n with 2 to skip them
        for (ulong n = 5; n <= SqrtLimit; n+=2) {
                if (isPrime[n]) {
                        ulong s = n * n;
                        for (ulong k = s; k <= limit; k += s) { isPrime[k] = false; }
                }
        }
        isPrime[2] = true;
        isPrime[3] = true;
}

Result:

Testing: SieveOfAtkin
Number of Prime : 664579
Execution time : 811 ms.

Testing: SieveOfAtkinFerencn
Number of Prime : 664579
Execution time : 468 ms.

Testing: SieveOfEratosthenesBaavgai
Number of Prime : 664579
Execution time : 328 ms.

Atkin still beaten, but by a slightly smaller margin...

This post has been edited by Ferencn: 01 March 2010 - 09:07 AM

[Tapas Bose]

Slightly optimized Sieve of Eratosthenes :

void SieveOfEratosthenes :: PrimeGen() 
{
        ulong SqrtLimit = (ulong)ceil(sqrt((double)Limit));
                	
        for (ulong i = 2; i <= SqrtLimit; i++) 
        { 
              if (IsPrime[i])  
              { 
                    for (ulong j = i+i; j <= Limit; j += i) 
                    { 
                          IsPrime[j] = false; 
                    } 
              }
        } 
}

Output:

Testing: Sieve Of Atkin
Number of Prime : 664579
Execution time : 920 ms.

Testing: Sieve Of Eratosthenes
Number of Prime : 664579
Execution time : 727 ms.