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?

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

### ← February 2016 →

S | M | T | W | T | F | S |
---|---|---|---|---|---|---|

1 | 2 | 3 | 4 | 5 | 6 | |

7 |
8
| 9 | 10 | 11 | 12 | 13 |

14 | 15 | 16 | 17 | 18 | 19 | 20 |

21 | 22 | 23 | 24 | 25 | 26 | 27 |

28 | 29 |

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

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

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

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

### Smiley of the [however often I change it]

### Contact Me

e-mail: [email protected]

Google Talk: [email protected]

MSN: [email protected]

Yahoo: gabehabe (rarely used)

AIM: gabehabe (rarely used)

Skype: gabehabe

Want me to work for you? [click]

Google Talk: [email protected]

MSN: [email protected]

Yahoo: gabehabe (rarely used)

AIM: gabehabe (rarely used)

Skype: gabehabe

Want me to work for you? [click]