Blog Entry (c) Friday, June 21, 2024, by James Pate Williams, Jr. Comparison of Two Prime Number Sieves

// PrimeSieveComparison.cpp (c) Friday, June 21, 2024
// by James Pate Williams, Jr.
//
//  SieveOfAtkin.java
//  SieveOfAtkin
//
//  Created by James Pate Williams, Jr. on 9/29/07.
//  Copyright (c) 2007 James Pate Williams, Jr. All rights reserved.
//
//  SieveOfEratosthenes.java
//  SieveOfEratosthenes
//
//  Created by James Pate Williams, Jr. on 9/29/07.
//  Copyright (c) 2007 James Pate Williams, Jr. All rights reserved.
//

#include <math.h>
#include <iostream>
#include <chrono>
using namespace std::chrono;
using namespace std;

const int Maximum = 100000000;
bool sieve[Maximum + 1];

void SieveOfAtkin(int limit)
{
	auto start = high_resolution_clock::now();
	int e, k, n, p, x, xx3, xx4, y, yy;
	int primeCount = 2, sqrtLimit = (int)sqrt(limit);

	for (n = 5; n <= limit; n++)
		sieve[n] = false;

	for (x = 1; x <= sqrtLimit; x++) {
		xx3 = 3 * x * x;
		xx4 = 4 * x * x;
		for (y = 1; y <= sqrtLimit; y++) {
			yy = y * y;
			n = xx4 + yy;
			if (n <= limit && (n % 12 == 1 || n % 12 == 5))
				sieve[n] = !sieve[n];
			n = xx3 + yy;
			if (n <= limit && n % 12 == 7)
				sieve[n] = !sieve[n];
			n = xx3 - yy;
			if (x > y && n <= limit && n % 12 == 11)
				sieve[n] = !sieve[n];
		}
	}

	for (n = 5; n <= sqrtLimit; n++) {
		if (sieve[n]) {
			e = 1;
			p = n * n;
			while (true) {
				k = e * p;
				if (k > limit)
					break;
				sieve[k] = false;
				e++;
			}
		}
	}
	
	for (n = 5; n <= limit; n++)
		if (sieve[n])
			primeCount++;

	auto stop = high_resolution_clock::now();
	auto duration = duration_cast<milliseconds>(stop - start);

	std::cout << "Number of primes <= " << limit << ' ';
	std::cout << primeCount << endl;
	std::cout << "Milliseconds taken by Sieve of Atkin: "
		<< duration.count() << endl;
}

void SieveOfEratosthenes(int limit)
{
	auto start = high_resolution_clock::now();
	int i = 0, k = 0, n = 0, nn = 0;
	int primeCount = 0, sqrtLimit = (int)sqrt(limit);

	// initialize the prime number sieve

	for (n = 2; n <= limit; n++)
		sieve[n] = true;

	// eliminate the multiples of n

	for (n = 2; n <= sqrtLimit; n++)
		for (i = 2; i <= n - 1; i++)
			sieve[i * n] = false;

	// eliminate squares

	for (n = 2; n <= sqrtLimit; n++) {
		if (sieve[n]) {
			k = 0;
			nn = n * n;
			i = nn + k * n;
			while (i <= limit) {
				sieve[i] = false;
				i = nn + k * n;
				k++;
			}
		}
	}

	primeCount = 0;

	for (n = 2; n <= limit; n++)
		if (sieve[n])
			primeCount++;

	auto stop = high_resolution_clock::now();
	auto duration = duration_cast<milliseconds>(stop - start);

	std::cout << "Number of primes <= " << limit << ' ';
	std::cout << primeCount << endl;
	std::cout << "Milliseconds taken by Sieve of Eratosthenes: "
		<< duration.count() << endl;
}

int main()
{
	while (true)
	{
		int limit = 0;
		std::cout << "Limit = ";
		cin >> limit;

		if (limit == 0)
			break;

		SieveOfAtkin(limit);
		SieveOfEratosthenes(limit);
	}

	return 0;
}