u*****o
发帖数: 1224 | 1 最近这道题很火爆！我找来貌似最EFFICIENT的CODE看（就是传说中的SIEVE OF
ERATOSHENES，多高端的名字！！），发现这么一行
请大家看第三行，第四行。。。为什么要用MEMSET这个function呢。。bool
array的话默认就是0吧。。。是不是为了省MEMORY呢？我直觉是。。。
走过路过的牛牛们指点一下吧。。。
void runEratosthenesSieve(int upperBound) {
int upperBoundSquareRoot = (int)sqrt((double)upperBound);
bool *isComposite = new bool[upperBound + 1];
memset(isComposite, 0, sizeof(bool) * (upperBound + 1));
for (int m = 2; m <= upperBoundSquareRoot; m++) {
if (!isComposite[m]) {
cout << m << " ";
for (int k = m * m; k <= upperBound; k += m)
isComposite[k] = true;
}
}
for (int m = upperBoundSquareRoot; m <= upperBound; m++)
if (!isComposite[m])
cout << m << " ";
delete [] isComposite;
} |
p*****2
发帖数: 21240 | |
u*****o
发帖数: 1224 | 3 这个就是找kth prime number的算法啊。。二爷咋会不知呢，又逗我这个傻姑娘了。。
。 |
p*****2
发帖数: 21240 | |
p*****2
发帖数: 21240 | |
r*********n
发帖数: 4553 | 6 upperBound是什么？比如让你找第999个prime number，你怎么确定upperBound呢？ |
r**h
发帖数: 1288 | 7 使用素数定理
【在 r*********n 的大作中提到】
: upperBound是什么？比如让你找第999个prime number，你怎么确定upperBound呢？
|
r*********n
发帖数: 4553 | 8 999/N = 1/lnN
这还要数值解一个超越方程，还不如用简单的primarity testing了
【在 r**h 的大作中提到】
: 使用素数定理
|
r**h
发帖数: 1288 | 9 the guys in GOOG will ask you to provide the upper bound otherwise you'll be
rejected lol
【在 r*********n 的大作中提到】
: 999/N = 1/lnN
: 这还要数值解一个超越方程，还不如用简单的primarity testing了
|
r*********n
发帖数: 4553 | 10 那只能说运气衰了
PS: 用简单的primarity testing，可以把已经找到的prime都存到一个hash set里面，
然后当set.size()==k的时候就停止。
be
【在 r**h 的大作中提到】
: the guys in GOOG will ask you to provide the upper bound otherwise you'll be
: rejected lol
|
|
|
s**x
发帖数: 7506 | 11 今早突然想到， 仍然用筛子， 原先是用一个数去筛掉所有不是的， 你可以建立一个
已经得到的素数的 vector, 然后对每个数用这个 vector 的数来除就可以了。
vector primes;
primes.push_back(2);
for (int i=3; primes.size() < K; i+=2) {
bool isprime = true;
for(int j=0; j < primes.size(); j++) {
if (i % primes[j] == 0) {
isprime = false;
break;
}
}
if (isprime) primes.pushback(i);
}
return primes[K-1]; :) |
r********d
发帖数: 7742 | 12 介个问题问得很natural！
【在 r*********n 的大作中提到】
: upperBound是什么？比如让你找第999个prime number，你怎么确定upperBound呢？
|
l*****s
发帖数: 774 | 13 二爷贴一下code吧，谢谢
【在 p*****2 的大作中提到】
: 这题我刚好昨天做了一下。能说说你的算法吗？
|
p*****2
发帖数: 21240 | 14
贴在另外一个帖子里了。你看看对不对。
【在 l*****s 的大作中提到】
: 二爷贴一下code吧，谢谢
|
u*****o
发帖数: 1224 | 15 好的，放到1楼了，的确不是找kth prime的，而是找1-N之间的所有素数。。囧
【在 p*****2 的大作中提到】
: 这题我刚好昨天做了一下。能说说你的算法吗？
|
u*****o
发帖数: 1224 | 16 是我没说清。。这题是找2-N之间的素数，不是找KTH PRIME的。。如果要找，是不是得
加个counter
【在 r*********n 的大作中提到】
: upperBound是什么？比如让你找第999个prime number，你怎么确定upperBound呢？
|
w**x
发帖数: 362 | 17 传统的 SIEVE OF ERATOSHENES
Time complexity 怎么分析？ wiki 是 nloglog(n) |
