Subscribe to gabehabe's on-topic ramblings

## Fast Prime Numbers

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;
}
```

S M T W T F S
12345
6789101112
13141516171819
20 212223242526
2728293031

### 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!

### 0 user(s) viewing

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

### gabehabe's off-topic ramblings

lol, my other blog died a horrible lonely death. Ah well.

### Contact Me

e-mail: [email protected]