Printable version of Entry

Quick entry, posting it for safe keeping.

I've already found this useful in a few of the problems over at http://projecteuler.net so I figured I'd share it. Quick primes! I actually wrote this a few days ago in response to http://www.dreamincode.net/forums/showtopic108683.htm (check it out, it's pretty interesting), before I realised what he was trying to do. (I was hasty!)

This program runs in silly time, something like a tenth of a second. Not bad for finding all primes up to 100,000 and finding the nth prime number, huh?

/*
 * A fast method of producing a table of primes
 * using a bitset
 * Author: Danny Battison
 */

 #include <iostream>
#include <bitset>
#include <cmath>

using namespace std;

#define MAX 100000

void output(bitset<MAX> primes) {
    for(int i = 0; i < MAX; i++) {
        if(primes[i] == 1) {
            cout << i << " ";
        }
    }
}

int get_nth_prime(int n, bitset<MAX> primes) {
    int count = 0;
    for(int i = 2; i < MAX; i++) {
        if(primes[i]) {
            count++;
        } if(count == n) {
            return i;
        }
    }
    return 0; // could not find
}

int main() {
    bitset <MAX> primes;
    for(int i = 1; i < MAX; i++) {
        primes[i] = 1;
    }
    // quick sieve of eratosthenes -- start it off
    int sieve[] = {2,3,5,7}; // give it a few primes to start with
    for(int mul = 0; mul < 4; mul++) {
        for(int i = 1; i < MAX; i++) {
            if(i % sieve[mul] == 0 && i != sieve[mul]) {
                primes[i] = 0;
            }
        }
    }

    // by now, we have a list of primes with some larger numbers still left
    // in order to remove those, we now need to run through primes and
    // make sure to remove multiples of primes up to sqrt(MAX)
    for(int i = 2; i < sqrt(MAX); i++) {
        if(primes[i]) {
            for(int j = i+1; j < MAX; j++) {
                if(j % i == 0) {
                    primes[j] = 0;
                }
            }
        }
    }

    cout << get_nth_prime(1000, primes);

    return 0;
}