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
← August 2017 →
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 | 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!
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)
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]