暂时没有时间整理，先放在这里：
http://www.quora.com/Prime-Numbers/What-are-good-ways-to-find-nth-prime-number-in-the-fastest-way
—————————————————————————————————————————————————————————————————————
This is an algorithm to test whether or not a given integer is prime. It's called the AKS primality test And can be done in polynomial time, which is usually considered a decent amount of time. Now if you're trying to compute the nth prime, it has been proven that the nth prime must be greater than 
and less than
When 
. So if you're searching for the nth prime, I'd look in this gap.
——————————————————————————————————————————————————————————————————————
If it is an interview question, I believe Sieve of Eratosthenes algorithm is a pretty good answer. For not too large n, the algorithm should work fine. For extremely large n, then you probably have to use a precomputed array of bins. Each covers a range of [i*N-i*(N+1)-1] and the number of prime numbers in that range as described in [2]. There is no general formula to compute nth prime number. [1] [2]
—————————————————————————————————————————————————————————————————————
附上一个同学写的用bitarray实现的求素数的方法：
/* * ======================================================================== * * Filename: bitset.h * * Description: bitset implementation in c. * * Created: 05/27/2013 11:09:43 PM * * Author: Fu Haiping (forhappy), haipingf@gmail.com * Company: ICT ( Institute Of Computing Technology, CAS ) * * ======================================================================== */#include/* for CHAR_BIT */#define BITMASK(b) (1 << ((b) % CHAR_BIT))#define BITSLOT(b) ((b) / CHAR_BIT)#define BITSET(a, b) ((a)[BITSLOT(b)] |= BITMASK(b))#define BITCLEAR(a, b) ((a)[BITSLOT(b)] &= ~BITMASK(b))#define BITTEST(a, b) ((a)[BITSLOT(b)] & BITMASK(b))#define BITNSLOTS(nb) ((nb + CHAR_BIT - 1) / CHAR_BIT)/* * char bitarray[BITNSLOTS(47)]; * BITSET(bitarray, 23); * if(BITTEST(bitarray, 35)) ... * * */#include #include #define MAX 10000int main(){ char bitarray[BITNSLOTS(MAX)]; int i, j; memset(bitarray, 0, BITNSLOTS(MAX)); for(i = 2; i < MAX; i++) { if(!BITTEST(bitarray, i)) { printf("%d\n", i); for(j = i + i; j < MAX; j += i) BITSET(bitarray, j); } } return 0;}
