s********u
发帖数: 1109 | 1 发现careercup上面面经的解答真是不忍直视，挺明了的思路经常有人写一长串代码，
乍看容易把人吓到。
我的思路是建立一个list存质数，然后对每个奇数检验(遍历一遍这个质数list），直
到这个list的size到N。
因为是经典题，所以想问问是否这个就是最优解法了。
list findNthPrime( int N ){
int prime = 2;
int num = 3;
list primes;
primes.push_back(2);
while( primes.size() < n){
for( list::iterator it = primes.begin(); it != primes.end() &&
*it <= (int) sqrt( num ); it++ ){
if( num%(*it) == 0 ){
num += 2;
it = primes.begin();
}
}
primes.push_back(num);
num += 2;
}
return primes;
}
|
s*******z
发帖数: 83 | 2 我卖弄一下吧, 请gg 筛法求素数~~~ 应该是比较快的.... |
s********u
发帖数: 1109 | 3 我搜了下，就是sieveOfErathenese吧？（从来拼不对。。）
可是这个只能解决小于N的素数，而不能解决第N个素数的问题啊。我想过先筛法，然后
不够的话再对bool数组翻倍。。再翻倍。。。但那样好像反而搞复杂了。。
【在 s*******z 的大作中提到】
: 我卖弄一下吧, 请gg 筛法求素数~~~ 应该是比较快的....
|
g**G
发帖数: 767 | 4 我一般就是筛一堆出来然后再在里面挑
N如果太大，大于Max array length，估计就只能存文件，然后太大不能筛的就一个一
个试了
【在 s********u 的大作中提到】
: 我搜了下，就是sieveOfErathenese吧？（从来拼不对。。）
: 可是这个只能解决小于N的素数，而不能解决第N个素数的问题啊。我想过先筛法，然后
: 不够的话再对bool数组翻倍。。再翻倍。。。但那样好像反而搞复杂了。。
|
s********u
发帖数: 1109 | 5 不是N太大的意思。而是比如要你找第100个质数，你怎么知道这第100个大致是在什么
范围呢？因为要知道这个范围，才能去开那个bool数组。
【在 g**G 的大作中提到】
: 我一般就是筛一堆出来然后再在里面挑
: N如果太大，大于Max array length，估计就只能存文件，然后太大不能筛的就一个一
: 个试了
|
h**6
发帖数: 4160 | 6 网上找了一个第x个素数的范围公式(x>=6)
xlnx + xlnlnx - x < p(x) < xlnx + xlnlnx |
s*****r
发帖数: 108 | |
A***o
发帖数: 358 | 8 如果允许漏掉一些质数，效率上可以做得比筛子法好很多，比如在第n个prime gap用
miller rabin找第一个质数作为第n个质数
【在 s********u 的大作中提到】
: 发现careercup上面面经的解答真是不忍直视，挺明了的思路经常有人写一长串代码，
: 乍看容易把人吓到。
: 我的思路是建立一个list存质数，然后对每个奇数检验(遍历一遍这个质数list），直
: 到这个list的size到N。
: 因为是经典题，所以想问问是否这个就是最优解法了。
: list findNthPrime( int N ){
: int prime = 2;
: int num = 3;
:
: list primes;
|
