经典题：找前N个质数# JobHunting - 待字闺中
s*u
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;
}
乍看容易把人吓到。
我的思路是建立一个list存质数，然后对每个奇数检验(遍历一遍这个质数list），直
到这个list的size到N。
因为是经典题，所以想问问是否这个就是最优解法了。
list
int prime = 2;
int num = 3;
list
primes.push_back(2);
while( primes.size() < n){
for( list
*it <= (int) sqrt( num ); it++ ){
if( num%(*it) == 0 ){
num += 2;
it = primes.begin();
}
}
primes.push_back(num);
num += 2;
}
return primes;
}
