谁还有 3* Vitality 或者 ZTE Score?# PDA - 掌中宝
h*3
1 楼
半年前碰到的, 一直不知道最优解:
写出N之内的所有素数.
就知道sieve of eratosthenes algorithm, :D.
对于大量数据,比如>10^7. 有更优解么?
写出N之内的所有素数.
就知道sieve of eratosthenes algorithm, :D.
对于大量数据,比如>10^7. 有更优解么?
V*9
2 楼
比如。。。
l*6
3 楼
有的请联系。谢谢。
g*x
4 楼
一个个找，看N有没有在之前找到的所有小于sqrt(N)的质数中能被整除的，如果没有则
N为质数，添加到质数list。。。时间复杂度O(N^1.5)，空间复杂度虽然也是O(N)，但
实际的质数会比N小得多，在N很大的情况下至少不那么容易stack overflow
N为质数，添加到质数list。。。时间复杂度O(N^1.5)，空间复杂度虽然也是O(N)，但
实际的质数会比N小得多，在N很大的情况下至少不那么容易stack overflow
b*d
5 楼
比如审核图片？
N*n
6 楼
I need one ZTE, thanks.
h*3
7 楼
时间复杂度为什么是N^1.5?
这个空间复杂度似乎是跑不掉的, 必须有这样大的storage. 如果很大, 内存不够, 是
铁顶OutOfMemmoryError的.
【在 g*****x 的大作中提到】
: 一个个找，看N有没有在之前找到的所有小于sqrt(N)的质数中能被整除的，如果没有则
: N为质数，添加到质数list。。。时间复杂度O(N^1.5)，空间复杂度虽然也是O(N)，但
: 实际的质数会比N小得多，在N很大的情况下至少不那么容易stack overflow
这个空间复杂度似乎是跑不掉的, 必须有这样大的storage. 如果很大, 内存不够, 是
铁顶OutOfMemmoryError的.
【在 g*****x 的大作中提到】
: 一个个找，看N有没有在之前找到的所有小于sqrt(N)的质数中能被整除的，如果没有则
: N为质数，添加到质数list。。。时间复杂度O(N^1.5)，空间复杂度虽然也是O(N)，但
: 实际的质数会比N小得多，在N很大的情况下至少不那么容易stack overflow
l*e
8 楼
比如可以卖血
l*6
9 楼
顶一下
a*7
10 楼
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.
Then 10^7 number only takes 10^7 bits/ (8*1024*1024) = 1.19 MB space.
b*m
11 楼
我有个盒子还没开封的，连蓝牙小音响一起的
t*v
12 楼
sieve of eratosthenes is good enough for interview.
【在 h******3 的大作中提到】
: 半年前碰到的, 一直不知道最优解:
: 写出N之内的所有素数.
: 就知道sieve of eratosthenes algorithm, :D.
: 对于大量数据,比如>10^7. 有更优解么?
【在 h******3 的大作中提到】
: 半年前碰到的, 一直不知道最优解:
: 写出N之内的所有素数.
: 就知道sieve of eratosthenes algorithm, :D.
: 对于大量数据,比如>10^7. 有更优解么?
c*r
13 楼
你好，请问你的vitality还有没有？卖多少钱？（连小音响一起）
【在 b******m 的大作中提到】
: 我有个盒子还没开封的，连蓝牙小音响一起的
【在 b******m 的大作中提到】
: 我有个盒子还没开封的，连蓝牙小音响一起的
g*x
14 楼
就是在验证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的.
这一个的复杂度是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的.
D*r
15 楼
同问。
g*s
16 楼
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，因此如果只保存所有的质数的话可以大大节省空间
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，因此如果只保存所有的质数的话可以大大节省空间
s*g
17 楼
我有一个，已经root了并刷到pageplus,装了不少软件，包括GPS软件。基本上我已经折
腾完了，你不需要再做什么。当时刷了pageplus有两块钱在里面，应该还没过期吧，反
正我从不用它打电话，都是用来听音乐。
腾完了，你不需要再做什么。当时刷了pageplus有两块钱在里面，应该还没过期吧，反
正我从不用它打电话，都是用来听音乐。
h*3
18 楼
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，因此如果只保存所有的质数的话可以大大节省空间
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，因此如果只保存所有的质数的话可以大大节省空间
l*6
19 楼
多少米出？
【在 b******m 的大作中提到】
: 我有个盒子还没开封的，连蓝牙小音响一起的
h*3
20 楼
yes.
for large data, need to be very careful, for example:
for(i=2;i
for(j=i;j*i
}
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.
for large data, need to be very careful, for example:
for(i=2;i
for(j=i;j*i
}
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.
b*g
21 楼
b*7
22 楼
这东西直接拿回国买张卡能打电话吗？
b*g
23 楼
不能。这是CDMA手机，你说得是GSM手机。
【在 b********7 的大作中提到】
: 这东西直接拿回国买张卡能打电话吗？
【在 b********7 的大作中提到】
: 这东西直接拿回国买张卡能打电话吗？
b*m
24 楼
大家去买bigdig的吧，我卖的比他的贵。。。。
相关阅读
freedompop friends 加一下啦突然一下安卓待机不行了，少一半待机Thunderbird 下面的MSN邮箱为何不能同步文件夹？？微软搞平板tradeln 居然不回收Surface一代Kindle Fire HDX狗狗什么时候花200把儿子都买回去啊Android 4.4新引入的那个ART比现在的dalvik能快多少？staighttalk买的iphone 5能直接上pp吗？ (转载)每年到年底又要关注gv转一个自用的lumia1020+全套配件Note 3 LCD screen 裂了net10的50块钱unlimited data速度快吗？Camera nokia 1020 v.s. Nexus 5N5 vs iPhone5 vs S4 in Camera Test Comparison想去店里买iphone5s跟mini2的可以用这个 (转载)今天去靶子店问了你们N5自认屌丝的三星note怪事请问verizon 3G ipad air可以用tmobile 200M plan吗？有人能推荐个国内可靠的Note 3淘宝卖家吗？