h******3
发帖数: 351 | 1 半年前碰到的, 一直不知道最优解:
写出N之内的所有素数.
就知道sieve of eratosthenes algorithm, :D.
对于大量数据,比如>10^7. 有更优解么? |
g*****x
发帖数: 799 | 2 一个个找，看N有没有在之前找到的所有小于sqrt(N)的质数中能被整除的，如果没有则
N为质数，添加到质数list。。。时间复杂度O(N^1.5)，空间复杂度虽然也是O(N)，但
实际的质数会比N小得多，在N很大的情况下至少不那么容易stack overflow |
h******3
发帖数: 351 | 3 时间复杂度为什么是N^1.5?
这个空间复杂度似乎是跑不掉的, 必须有这样大的storage. 如果很大, 内存不够, 是
铁顶OutOfMemmoryError的.
【在 g*****x 的大作中提到】
: 一个个找，看N有没有在之前找到的所有小于sqrt(N)的质数中能被整除的，如果没有则
: N为质数，添加到质数list。。。时间复杂度O(N^1.5)，空间复杂度虽然也是O(N)，但
: 实际的质数会比N小得多，在N很大的情况下至少不那么容易stack overflow
|
a******7
发帖数: 106 | 4 can we use bitmap of true of false to indicate ith number is prime or not?
Then 10^7 number only takes 10^7 bits/ (8*1024*1024) = 1.19 MB space. |
t**v
发帖数: 101 | 5 sieve of eratosthenes is good enough for interview.
【在 h******3 的大作中提到】
: 半年前碰到的, 一直不知道最优解:
: 写出N之内的所有素数.
: 就知道sieve of eratosthenes algorithm, :D.
: 对于大量数据,比如>10^7. 有更优解么?
|
g*****x
发帖数: 799 | 6 就是在验证K是不是质数的时候只要看是否能被比sqrt(K)小的质数整除就行了，所以查
这一个的复杂度是O(N^0.5)，而共有N个数要验证，就是O(N*N^1/2)了。。。比起sieve
of eratosthenes的O(N)是要慢很多了
但是用sieve of eratosthenes的话要用N/8个byte的空间，而当N很大时质数在数据集
里的分布相当稀疏，远远没有N/8，因此如果只保存所有的质数的话可以大大节省空间
【在 h******3 的大作中提到】
: 时间复杂度为什么是N^1.5?
: 这个空间复杂度似乎是跑不掉的, 必须有这样大的storage. 如果很大, 内存不够, 是
: 铁顶OutOfMemmoryError的.
|
g*********s
发帖数: 1782 | 7 if prime is sparse, how do u know # of prime less than N is O(N^0.5)? why
can't it be O(N^0.25) or O(lgN)?
sieve
【在 g*****x 的大作中提到】
: 就是在验证K是不是质数的时候只要看是否能被比sqrt(K)小的质数整除就行了，所以查
: 这一个的复杂度是O(N^0.5)，而共有N个数要验证，就是O(N*N^1/2)了。。。比起sieve
: of eratosthenes的O(N)是要慢很多了
: 但是用sieve of eratosthenes的话要用N/8个byte的空间，而当N很大时质数在数据集
: 里的分布相当稀疏，远远没有N/8，因此如果只保存所有的质数的话可以大大节省空间
|
h******3
发帖数: 351 | 8 sorry, I can't input Chinese now.
I remember reading the idea of "验证K是不是质数的时候只要看是否能被比sqrt(K)
小的质数整除就行了" somewhere. what is the name of the theory? In order to
know all the primes that are less than sqrt(k) when k is 10^7, we might need
temporary storage, such as array.
sieve
【在 g*****x 的大作中提到】
: 就是在验证K是不是质数的时候只要看是否能被比sqrt(K)小的质数整除就行了，所以查
: 这一个的复杂度是O(N^0.5)，而共有N个数要验证，就是O(N*N^1/2)了。。。比起sieve
: of eratosthenes的O(N)是要慢很多了
: 但是用sieve of eratosthenes的话要用N/8个byte的空间，而当N很大时质数在数据集
: 里的分布相当稀疏，远远没有N/8，因此如果只保存所有的质数的话可以大大节省空间
|
h******3
发帖数: 351 | 9 yes.
for large data, need to be very careful, for example:
for(i=2;i
if(a[i]!=false)
for(j=i;j*i
a[i*j]=false;
}
if i*j can't be represented by int, overflow, the code will throw
ArrayIndexOutOfBoundsException.
one way is to check i*j>0, but it would affect performance
one way is changing from int to long, but if affect array indexing.
not sure whether there are perfect solution?
【在 t**v 的大作中提到】
: sieve of eratosthenes is good enough for interview.
|
