计算第K个素数

暂时没有时间整理，先放在这里：

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 http://en.m.wikipedia.org/wiki/A...

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] http://en.wikipedia.org/wiki/Sie...
[2] http://primes.utm.edu/nthprime/a...

———————————————————————————————————————————————————————————————————————

附上一个同学写的用bitarray实现的http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes求素数的方法：

/*

 * ========================================================================

 *

 *       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 <limits.h>     /* 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 <stdio.h>

#include <string.h>

#define MAX 10000

int main()

{

    char bitarray[BITNSLOTS(MAX)];

    int i, j;

    memset(bitarray, , BITNSLOTS(MAX));

    for(i = ; i < MAX; i++) {

        if(!BITTEST(bitarray, i)) {

            printf("%d\n", i);

            for(j = i + i; j < MAX; j += i)

                BITSET(bitarray, j);

        }

    }

    return ;

}

巴特西

计算第K个素数

最新文章

热门文章