First the C++ results:
Limit = 1000000
Number of primes <= 1000000 78498
Milliseconds taken by Sieve of Atkin: 12
Number of primes <= 1000000 78498
Milliseconds taken by Sieve of Eratosthenes: 14
Limit = 10000000
Number of primes <= 10000000 664579
Milliseconds taken by Sieve of Atkin: 159
Number of primes <= 10000000 664579
Milliseconds taken by Sieve of Eratosthenes: 204
Limit = 100000000
Number of primes <= 100000000 5761455
Milliseconds taken by Sieve of Atkin: 1949
Number of primes <= 100000000 5761455
Milliseconds taken by Sieve of Eratosthenes: 2343
Limit = 0
Next, we have the Java results:
C:\WINDOWS\system32>java -jar k:\SieveOfAtkin\build\Debug\SieveOfAtkin.jar 1000000 0
number of primes less than equal 1000000 = 78498
total computation time in seconds = 0.008
C:\WINDOWS\system32>java -jar k:\SieveOfAtkin\build\Debug\SieveOfAtkin.jar 10000000 0
number of primes less than equal 10000000 = 664579
total computation time in seconds = 0.098
C:\WINDOWS\system32>java -jar k:\SieveOfEratosthenes\build\Debug\SieveOfEratosthenes.jar 1000000 0
number of primes less than equal 1000000 = 78498
total computation time in seconds = 0.011
C:\WINDOWS\system32>java -jar k:\SieveOfEratosthenes\build\Debug\SieveOfEratosthenes.jar 10000000 0
number of primes less than equal 10000000 = 664579
total computation time in seconds = 0.151
C:\WINDOWS\system32>java -jar k:\SieveOfAtkin\build\Debug\SieveOfAtkin.jar 100000000 0
number of primes less than equal 100000000 = 5761455
total computation time in seconds = 1.511
C:\WINDOWS\system32>java -jar k:\SieveOfEratosthenes\build\Debug\SieveOfEratosthenes.jar 100000000 0
number of primes less than equal 100000000 = 5761455
total computation time in seconds = 1.995
Notice that the Java application outperforms the C++ application.
// 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;
}
Numerical Explorations 