Programming and general geekiness.

Those that read my blogs regularly will know that I’ve had a bit of a recent obsession with prime numbers. I am really not sure why, but I have been doing a lot of programming with them. My original method had been to use modulus and check if a number was divisible by any already known prime numbers. I wrote this in Java and it it took an hour to generate all the primes up to 10,000,000. My next approach was to write a small Python program that used the Sieve of Eratosthenes where by you loop through the multiples of each number marking them as non-prime. This method works well but it is still quite slow.

My next approach, therefore, is to use the Sieve of Atkin. This is a relatively modern method that is highly efficient. Here I have implemented it in C++:

#include <iostream>
#include <cmath>
#include <fstream>
using namespace std;
int main (int argc, char* argv[])
{
 //Create the various different variables required
 int limit = 1000000;
 int root = ceil(sqrt(limit));
 bool sieve[limit];
 int primes[(limit/2)+1];
 int insert = 2;
 primes[0] = 2;
 primes[1] = 3;
 for (int z = 0; z < limit; z++) sieve[z] = false; //Not all compilers have false as the default boolean value
 for (int x = 1; x <= root; x++)
 {
 for (int y = 1; y <= root; y++)
 {
 //Main part of Sieve of Atkin
 int n = (4*x*x)+(y*y);
 if (n <= limit && (n % 12 == 1 || n % 12 == 5)) sieve[n] ^= true;
 n = (3*x*x)+(y*y);
 if (n <= limit && n % 12 == 7) sieve[n] ^= true;
 n = (3*x*x)-(y*y);
 if (x > y && n <= limit && n % 12 == 11) sieve[n] ^= true;
 }
 }
 //Mark all multiples of squares as non-prime
 for (int r = 5; r <= root; r++) if (sieve[r]) for (int i = r*r; i < limit; i += r*r) sieve[i] = false;
 //Add into prime array
 for (int a = 5; a < limit; a++)
 {
 if (sieve[a])
 {
 primes[insert] = a;
 insert++;
 }
 }
 //The following code just writes the array to a file
 ofstream file;
 char filename[100];
 sprintf(filename, "primes_%d.txt", limit);
 file.open(filename);
 for (int a = 0; a < insert; a++) file << primes[a] << ((a == insert-1) ? "" : "\n");
 file.close();
 cout << "Written to file.\n";
 return 0;
}

This method works incredibly well and is capable of producing primes in fractions of a seconds. Click here to download the source code.

Advertisements

Comments on: "Generating primes with the Sieve of Atkin in C++" (1)

  1. […] numbers. I haven't been able to find any existing VB code, so I have based my algorithm on this C++ implementation. My function is not correctly marking all the primes. For example, when I try to find the prime […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: