l*****s
发帖数: 774 | 1 今天看了这个帖子
http://www.mitbbs.com/article_t/JobHunting/32475925.html
里面有一题就是 find Kth prime number，目前我能想到的方法就是wiki上面的那个方
法，从2开始循环，依次除去2的倍数，3的倍数，5的倍数，等等。然后找到第Kth，这
个时候要一直循环到N，N远大于K。
另外一种方法，就是依次循环找prime，然后再设置一个count计数，这个方法还不如第
一个那。
请问有没有更好的方法？谢谢 |
g**G
发帖数: 767 | 2 Sieve of Eratosthenes 已经很好了，如果只是面试，这个应该足够
再优化可以看看其他的sieve方法，在wiki下面有 |
n****n
发帖数: 568 | 3 but how do we find N to make sure the k-th prime is less than N?
【在 g**G 的大作中提到】
: Sieve of Eratosthenes 已经很好了，如果只是面试，这个应该足够
: 再优化可以看看其他的sieve方法，在wiki下面有
|
p*****2
发帖数: 21240 | 4
是15280063吗？大概2，3秒吧。
【在 l*****s 的大作中提到】
: 今天看了这个帖子
: http://www.mitbbs.com/article_t/JobHunting/32475925.html
: 里面有一题就是 find Kth prime number，目前我能想到的方法就是wiki上面的那个方
: 法，从2开始循环，依次除去2的倍数，3的倍数，5的倍数，等等。然后找到第Kth，这
: 个时候要一直循环到N，N远大于K。
: 另外一种方法，就是依次循环找prime，然后再设置一个count计数，这个方法还不如第
: 一个那。
: 请问有没有更好的方法？谢谢
|
p*****2
发帖数: 21240 | |
l*****s
发帖数: 774 | 6 第二种方法的话是不是 对于一个数 k，验证它是不是prime number，从 sqrt(k) 往小
的方向循环，一直循环到2，如果中间有可以整除的数字，立即break，这样的复杂度很
大吧。谢谢
不知道二爷是否可以贴个code来看看
【在 p*****2 的大作中提到】
: 你说的第二种方法就可以了。
|
p*****2
发帖数: 21240 | 7
大牛看看对不对
int findPrime(int count){
ArrayList al=new ArrayList();
int i=1;
loop:
while(count>0){
i++;
for(int j=0;j
if(i%al.get(j)==0){
continue loop;
}
}
al.add(i);
count--;
}
return al.get(al.size()-1);
}
【在 l*****s 的大作中提到】
: 第二种方法的话是不是 对于一个数 k，验证它是不是prime number，从 sqrt(k) 往小
: 的方向循环，一直循环到2，如果中间有可以整除的数字，立即break，这样的复杂度很
: 大吧。谢谢
: 不知道二爷是否可以贴个code来看看
|
l*****s
发帖数: 774 | 8 惭愧，俺是半路出家的，
这样把所有都找过的 prime number都存起来，不浪费空间吗？谢谢
这个复杂度算是多少？谢谢
【在 p*****2 的大作中提到】
:
: 大牛看看对不对
: int findPrime(int count){
: ArrayList al=new ArrayList();
: int i=1;
: loop:
: while(count>0){
: i++;
: for(int j=0;j: if(i%al.get(j)==0){
|
M********o
发帖数: 13 | |
w**x
发帖数: 362 | |
p*****2
发帖数: 21240 | 11
按照原题，空间直需要几M, 很少，时间大概2-3秒，很快的。我是在mac上测试的。
【在 l*****s 的大作中提到】
: 惭愧，俺是半路出家的，
: 这样把所有都找过的 prime number都存起来，不浪费空间吗？谢谢
: 这个复杂度算是多少？谢谢
|
p*****2
发帖数: 21240 | 12
大牛有整出了没听说过的算法了。有时间学习一下。
【在 M********o 的大作中提到】
: 二爷的code很好，算法应该算Trial division一类。
: 这个帖子有详细的讨论，还牵涉到许多数论的东西。
: http://stackoverflow.com/questions/9625663/calculating-and-prin
|
u*****o
发帖数: 1224 | 13 二爷我想问问你的CODE中
loop:
...
... continue loop;
这种CONTINUE IN OUTER LOOP (while loop NOT the for loop)C++里可以这么用吗？
就是自己DEFINE SKIP后从哪里ITERATE。。我搜关键字没搜出来，我一直不清楚这种
CASE这么处理，机缘巧合竟然在这道题里看到这么用了。。
【在 p*****2 的大作中提到】
:
: 大牛有整出了没听说过的算法了。有时间学习一下。
|
p*****2
发帖数: 21240 | 14
用goto可以吧？
【在 u*****o 的大作中提到】
: 二爷我想问问你的CODE中
: loop:
: ...
: ... continue loop;
: 这种CONTINUE IN OUTER LOOP (while loop NOT the for loop)C++里可以这么用吗？
: 就是自己DEFINE SKIP后从哪里ITERATE。。我搜关键字没搜出来，我一直不清楚这种
: CASE这么处理，机缘巧合竟然在这道题里看到这么用了。。
|
