Subscribe to gabehabe's on-topic ramblings        RSS Feed
-----

Fast Prime Numbers

Icon Leave Comment
Quick entry, posting it for safe keeping. :)

I've already found this useful in a few of the problems over at project euler so I figured I'd share it. Quick primes! I actually wrote this a few days ago in response to NickDMax's thread (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;
}

0 Comments On This Entry

 

July 2014

S M T W T F S
  12345
6789101112
13141516171819
20212223242526
272829 30 31  

Request A Topic!

Want me to blog about something? Perhaps a language? A piece of software? A specific topic? Let me know! Even guests can post here on my blog!

If you would like to request a topic, please post a comment here and I'll get on it right away! smile.gif

Search My Blog

0 user(s) viewing

0 Guests
0 member(s)
0 anonymous member(s)

gabehabe's off-topic ramblings

Follow me on Twitter!
lol, my other blog died a horrible lonely death. Ah well.

Smiley of the [however often I change it]

IPB Image

Contact Me

e-mail: gabehabe@gmail.com

Google Talk: gabehabe@gmail.com
MSN: gabehabe@hotmail.com
Yahoo: gabehabe (rarely used)
AIM: gabehabe (rarely used)

Skype: gabehabe

Want me to work for you? [click]