Re: 我是StephenKing, 密码是abcdefg8，字母全部小写 (转载)# Joke - 肚皮舞运动
w*o
1 楼
1. 如何判断一个数是不是质数？
2. 如何求第n个(nth)质数？
对于上面的两道题，有什么快的算法和实现？
谢谢！
2. 如何求第n个(nth)质数？
对于上面的两道题，有什么快的算法和实现？
谢谢！
b*y
2 楼
有人重做过么？不是简单的re-surface。因为有些地方有些下陷了。
m*d
3 楼
【 以下文字转载自 Dreamer 讨论区 】
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标 题: Re: 我是StephenKing, 密码是abcdefg8，字母全部小写
发信站: BBS 未名空间站 (Wed Nov 2 03:43:08 2011, 美东)
你个傻逼，这招zy小姑娘就玩过了，你连新招都不会就来扯淡。
发信人: Dreamer (不要问我从哪里来), 信区: Dreamer
标 题: Re: 我是StephenKing, 密码是abcdefg8，字母全部小写
发信站: BBS 未名空间站 (Wed Nov 2 03:43:08 2011, 美东)
你个傻逼，这招zy小姑娘就玩过了，你连新招都不会就来扯淡。
S*w
4 楼
第一个是看能不能被1 到 sqrt（num）的数整除？
【在 w****o 的大作中提到】
: 1. 如何判断一个数是不是质数？
: 2. 如何求第n个(nth)质数？
: 对于上面的两道题，有什么快的算法和实现？
: 谢谢！
【在 w****o 的大作中提到】
: 1. 如何判断一个数是不是质数？
: 2. 如何求第n个(nth)质数？
: 对于上面的两道题，有什么快的算法和实现？
: 谢谢！
s*y
5 楼
you can do mudjacking if only part of your driveway sank.
【在 b**********y 的大作中提到】
: 有人重做过么？不是简单的re-surface。因为有些地方有些下陷了。
【在 b**********y 的大作中提到】
: 有人重做过么？不是简单的re-surface。因为有些地方有些下陷了。
g*e
6 楼
第二个，假设n是质数，那么所有n的倍数都不是质数。
维护一个array，从1开始数，找到一个质数就把所有它的倍数都标为合数。这样速度比
较快。不过要估计array大小
维护一个array，从1开始数，找到一个质数就把所有它的倍数都标为合数。这样速度比
较快。不过要估计array大小
b*y
7 楼
我家driveway是沥青的，不是水泥的。
w*z
8 楼
好像只要看能否被质数整除就行了吧。
如果不能被2，整除，那也不可能被4， 6， 8。。。整除。
上次面试，就栽这山了。
【在 S*******w 的大作中提到】
: 第一个是看能不能被1 到 sqrt（num）的数整除？
如果不能被2，整除，那也不可能被4， 6， 8。。。整除。
上次面试，就栽这山了。
【在 S*******w 的大作中提到】
: 第一个是看能不能被1 到 sqrt（num）的数整除？
N*s
9 楼
we spent $4250 totally paving asphalt driveway appx. 195ft x 10ft.
S*w
10 楼
嗯 不过怎么判断啊
【在 w**z 的大作中提到】
: 好像只要看能否被质数整除就行了吧。
: 如果不能被2，整除，那也不可能被4， 6， 8。。。整除。
: 上次面试，就栽这山了。
【在 w**z 的大作中提到】
: 好像只要看能否被质数整除就行了吧。
: 如果不能被2，整除，那也不可能被4， 6， 8。。。整除。
: 上次面试，就栽这山了。
D*9
11 楼
so how much to build a highway?
【在 N**s 的大作中提到】
: we spent $4250 totally paving asphalt driveway appx. 195ft x 10ft.
【在 N**s 的大作中提到】
: we spent $4250 totally paving asphalt driveway appx. 195ft x 10ft.
w*z
12 楼
搞个Array, 把以知的质数都存起来。就象第二题那样的解法。只是Array只能到一定大，总有超过的时候。
【在 S*******w 的大作中提到】
: 嗯 不过怎么判断啊
【在 S*******w 的大作中提到】
: 嗯 不过怎么判断啊
h*t
13 楼
Are you re-building or just add another layer? It seems cheap. And which
state are you in?
【在 N**s 的大作中提到】
: we spent $4250 totally paving asphalt driveway appx. 195ft x 10ft.
state are you in?
【在 N**s 的大作中提到】
: we spent $4250 totally paving asphalt driveway appx. 195ft x 10ft.
C*a
14 楼
1. it is a prime only if it does not have any prime factor that is less
than the root of itself.
2. Assume we had found out the first (n-1) primes, store them in an array (
or a list), and then check the numbers(>(n-1)th prime) to see if it is a
prime ( use 1. to judge).
【在 w****o 的大作中提到】
: 1. 如何判断一个数是不是质数？
: 2. 如何求第n个(nth)质数？
: 对于上面的两道题，有什么快的算法和实现？
: 谢谢！
than the root of itself.
2. Assume we had found out the first (n-1) primes, store them in an array (
or a list), and then check the numbers(>(n-1)th prime) to see if it is a
prime ( use 1. to judge).
【在 w****o 的大作中提到】
: 1. 如何判断一个数是不是质数？
: 2. 如何求第n个(nth)质数？
: 对于上面的两道题，有什么快的算法和实现？
: 谢谢！
b*y
15 楼
谢谢！你家的是我家的三倍大了，羡慕豪宅呀。那看来我家的差不多要$1500左右了。
【在 N**s 的大作中提到】
: we spent $4250 totally paving asphalt driveway appx. 195ft x 10ft.
【在 N**s 的大作中提到】
: we spent $4250 totally paving asphalt driveway appx. 195ft x 10ft.
n*0
16 楼
这里有比较详细的讨论
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
【在 w****o 的大作中提到】
: 1. 如何判断一个数是不是质数？
: 2. 如何求第n个(nth)质数？
: 对于上面的两道题，有什么快的算法和实现？
: 谢谢！
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
【在 w****o 的大作中提到】
: 1. 如何判断一个数是不是质数？
: 2. 如何求第n个(nth)质数？
: 对于上面的两道题，有什么快的算法和实现？
: 谢谢！
b*y
17 楼
原来不是在问我。
【在 h********t 的大作中提到】
: Are you re-building or just add another layer? It seems cheap. And which
: state are you in?
【在 h********t 的大作中提到】
: Are you re-building or just add another layer? It seems cheap. And which
: state are you in?
e*l
18 楼
还有高级一点的随机算法，Miller-Rabin，知道的话应该能加分
N*s
19 楼
Rebuilding. VA
【在 h********t 的大作中提到】
: Are you re-building or just add another layer? It seems cheap. And which
: state are you in?
【在 h********t 的大作中提到】
: Are you re-building or just add another layer? It seems cheap. And which
: state are you in?
w*z
20 楼
只有学数学的才会知道这个吧。估计面你的都不一定会知道。
【在 e***l 的大作中提到】
: 还有高级一点的随机算法，Miller-Rabin，知道的话应该能加分
【在 e***l 的大作中提到】
: 还有高级一点的随机算法，Miller-Rabin，知道的话应该能加分
b*y
21 楼
我晕，你要建highway?
【在 D****9 的大作中提到】
: so how much to build a highway?
【在 D****9 的大作中提到】
: so how much to build a highway?
S*w
22 楼
搞密码的都懂
【在 w**z 的大作中提到】
: 只有学数学的才会知道这个吧。估计面你的都不一定会知道。
【在 w**z 的大作中提到】
: 只有学数学的才会知道这个吧。估计面你的都不一定会知道。
N*s
23 楼
乡下小房，地大, 不值钱的 ：）
【在 b**********y 的大作中提到】
: 谢谢！你家的是我家的三倍大了，羡慕豪宅呀。那看来我家的差不多要$1500左右了。
【在 b**********y 的大作中提到】
: 谢谢！你家的是我家的三倍大了，羡慕豪宅呀。那看来我家的差不多要$1500左右了。
w*z
24 楼
俺只会用BASE64，哈哈
【在 S*******w 的大作中提到】
: 搞密码的都懂
【在 S*******w 的大作中提到】
: 搞密码的都懂
H*e
25 楼
对第二题，
如果用消除prime的倍数的方法，如何一开始确定array的size呢
如果说n=1000,你取范围的大小为多少？
【在 w****o 的大作中提到】
: 1. 如何判断一个数是不是质数？
: 2. 如何求第n个(nth)质数？
: 对于上面的两道题，有什么快的算法和实现？
: 谢谢！
如果用消除prime的倍数的方法，如何一开始确定array的size呢
如果说n=1000,你取范围的大小为多少？
【在 w****o 的大作中提到】
: 1. 如何判断一个数是不是质数？
: 2. 如何求第n个(nth)质数？
: 对于上面的两道题，有什么快的算法和实现？
: 谢谢！
p*2
26 楼
用ArrayList不就行了？
【在 H***e 的大作中提到】
: 对第二题，
: 如果用消除prime的倍数的方法，如何一开始确定array的size呢
: 如果说n=1000,你取范围的大小为多少？
H*e
27 楼
不是
你可能没明白我的意思
比如你要求第1000的质数
你初始的测试范围是1到多少？10000? 20000?
如果太小，导致不够，就还得扩展，然后把扩展的数一个一个的看能不能被前面的质素
整除，有点麻烦
【在 p*****2 的大作中提到】
:
: 用ArrayList不就行了？
你可能没明白我的意思
比如你要求第1000的质数
你初始的测试范围是1到多少？10000? 20000?
如果太小，导致不够，就还得扩展，然后把扩展的数一个一个的看能不能被前面的质素
整除，有点麻烦
【在 p*****2 的大作中提到】
:
: 用ArrayList不就行了？
p*2
28 楼
public static void main(String[] args)
{
ArrayList primes=new ArrayList();
int n=100;
primes.add(2);
for(int i=3;i<=Integer.MAX_VALUE;i+=2)
{
int j=0;
boolean fprime=true;
for(;j
int k=primes.get(j);
if(k>Math.sqrt(i))
break;
if(i%k==0)
{
fprime=false;
break;
}
}
if(fprime)
{
primes.add(i);
if(primes.size()==n)
break;
}
}
for(int i:primes)
System.out.print(i+" ");
}
{
ArrayList
int n=100;
primes.add(2);
for(int i=3;i<=Integer.MAX_VALUE;i+=2)
{
int j=0;
boolean fprime=true;
for(;j
int k=primes.get(j);
if(k>Math.sqrt(i))
break;
if(i%k==0)
{
fprime=false;
break;
}
}
if(fprime)
{
primes.add(i);
if(primes.size()==n)
break;
}
}
for(int i:primes)
System.out.print(i+" ");
}
p*2
29 楼
看我代码行不行。
【在 H***e 的大作中提到】
: 不是
: 你可能没明白我的意思
: 比如你要求第1000的质数
: 你初始的测试范围是1到多少？10000? 20000?
: 如果太小，导致不够，就还得扩展，然后把扩展的数一个一个的看能不能被前面的质素
: 整除，有点麻烦
H*e
30 楼
几个优化：
1。只要测试到sqrt(i)就可以了
2。每个数都测试从2开始有点浪费了。 可以在得到2的时候，直接把它所有的倍数化掉
，这样以后就不用测试6的倍数了之类的。
这也是我问初始用来划的array size取多少合适.
===========
public static void main(String[] args)
{
ArrayList primes=new ArrayList();
int n=100;
primes.add(2);
for(int i=3;i<=Integer.MAX_VALUE;i+=2)
{
int j=0;
for(;j
break;
if(j==primes.size())
primes.add(i);
if(primes.size()==n)
break;
}
for(int i:primes)
System.out.print(i+" ");
}
1。只要测试到sqrt(i)就可以了
2。每个数都测试从2开始有点浪费了。 可以在得到2的时候，直接把它所有的倍数化掉
，这样以后就不用测试6的倍数了之类的。
这也是我问初始用来划的array size取多少合适.
===========
public static void main(String[] args)
{
ArrayList
int n=100;
primes.add(2);
for(int i=3;i<=Integer.MAX_VALUE;i+=2)
{
int j=0;
for(;j
break;
if(j==primes.size())
primes.add(i);
if(primes.size()==n)
break;
}
for(int i:primes)
System.out.print(i+" ");
}
p*2
31 楼
1. 确实应该优化
2. 我对2进行了优化，从3开始 i+=2, 这样只检查奇数
你是想把3的倍数也话掉，然后5的倍数也划掉吗？这样意义大吗？你划掉不也得进行运
算吗？
【在 H***e 的大作中提到】
: 几个优化：
: 1。只要测试到sqrt(i)就可以了
: 2。每个数都测试从2开始有点浪费了。 可以在得到2的时候，直接把它所有的倍数化掉
: ，这样以后就不用测试6的倍数了之类的。
: 这也是我问初始用来划的array size取多少合适.
: ===========
: public static void main(String[] args)
: {
: ArrayList
: int n=100;
p*2
32 楼
我明白你的意思了。上边有人提到消除倍数的方法。这个方法不一定实用吧？
【在 H***e 的大作中提到】
: 对第二题，
: 如果用消除prime的倍数的方法，如何一开始确定array的size呢
: 如果说n=1000,你取范围的大小为多少？
H*e
33 楼
大啊。
你用一个array保存flag，如果已经被划掉了，根本不用再做 % 运算了，省了很多计算
【在 p*****2 的大作中提到】
:
: 我明白你的意思了。上边有人提到消除倍数的方法。这个方法不一定实用吧？
你用一个array保存flag，如果已经被划掉了，根本不用再做 % 运算了，省了很多计算
【在 p*****2 的大作中提到】
:
: 我明白你的意思了。上边有人提到消除倍数的方法。这个方法不一定实用吧？
p*2
34 楼
我做题的时候基本这样就可以了。你说的这个是用空间换时间，但是就是你说的那个问
题好像没法解决。
【在 H***e 的大作中提到】
: 大啊。
: 你用一个array保存flag，如果已经被划掉了，根本不用再做 % 运算了，省了很多计算
l*a
35 楼
得面试官认为可以才可以
【在 p*****2 的大作中提到】
:
: 我做题的时候基本这样就可以了。你说的这个是用空间换时间，但是就是你说的那个问
: 题好像没法解决。
【在 p*****2 的大作中提到】
:
: 我做题的时候基本这样就可以了。你说的这个是用空间换时间，但是就是你说的那个问
: 题好像没法解决。
p*2
36 楼
很多时候你也不知道面试官认可不认可，除非最后拿到offer。呵呵。
【在 l*****a 的大作中提到】
: 得面试官认为可以才可以
l*a
37 楼
比方说对于3，6,9,12,15,18,21,27。。。...已经是非质数，下次就不用判断9,15,21,27等
的倍数了
bool flag[]=new bool[n];
for(int i=0;i
if(flag[i]==false) continue;
k=2;
while(i*k
if (flag[i*k]) flag[i*k]=false;
k++;
}
}
【在 p*****2 的大作中提到】
:
: 很多时候你也不知道面试官认可不认可，除非最后拿到offer。呵呵。
的倍数了
bool flag[]=new bool[n];
for(int i=0;i
if(flag[i]==false) continue;
k=2;
while(i*k
if (flag[i*k]) flag[i*k]=false;
k++;
}
}
【在 p*****2 的大作中提到】
:
: 很多时候你也不知道面试官认可不认可，除非最后拿到offer。呵呵。
l*a
38 楼
其实，拿到offer也不见得你所有题都答对了
不过是人家认可了你的能力。。。
【在 p*****2 的大作中提到】
:
: 很多时候你也不知道面试官认可不认可，除非最后拿到offer。呵呵。
不过是人家认可了你的能力。。。
【在 p*****2 的大作中提到】
:
: 很多时候你也不知道面试官认可不认可，除非最后拿到offer。呵呵。
p*2
39 楼
21,27等
你这个也没有解决那个问题吧？就是如何定义n的问题。
【在 l*****a 的大作中提到】
: 比方说对于3，6,9,12,15,18,21,27。。。...已经是非质数，下次就不用判断9,15,21,27等
: 的倍数了
: bool flag[]=new bool[n];
: for(int i=0;i
: if(flag[i]==false) continue;
: k=2;
: while(i*k
l*a
40 楼
对，就是说用这个办法不太好确定初始大小。
或许只能用你的办法，动态追加。但中间的处理确实不如那个优化。
所以还要再思考
【在 p*****2 的大作中提到】
:
: 21,27等
: 你这个也没有解决那个问题吧？就是如何定义n的问题。
或许只能用你的办法，动态追加。但中间的处理确实不如那个优化。
所以还要再思考
【在 p*****2 的大作中提到】
:
: 21,27等
: 你这个也没有解决那个问题吧？就是如何定义n的问题。
f*l
41 楼
这里有一个解法
http://primes.utm.edu/nthprime/algorithm.php
如今所知的质数有限，应该直接用table把所有的都存起来，需要第几个，直接去取好
了。
【在 l*****a 的大作中提到】
: 对，就是说用这个办法不太好确定初始大小。
: 或许只能用你的办法，动态追加。但中间的处理确实不如那个优化。
: 所以还要再思考
http://primes.utm.edu/nthprime/algorithm.php
如今所知的质数有限，应该直接用table把所有的都存起来，需要第几个，直接去取好
了。
【在 l*****a 的大作中提到】
: 对，就是说用这个办法不太好确定初始大小。
: 或许只能用你的办法，动态追加。但中间的处理确实不如那个优化。
: 所以还要再思考
m*l
42 楼
质数是无限的
【在 f*******l 的大作中提到】
: 这里有一个解法
: http://primes.utm.edu/nthprime/algorithm.php
: 如今所知的质数有限，应该直接用table把所有的都存起来，需要第几个，直接去取好
: 了。
【在 f*******l 的大作中提到】
: 这里有一个解法
: http://primes.utm.edu/nthprime/algorithm.php
: 如今所知的质数有限，应该直接用table把所有的都存起来，需要第几个，直接去取好
: 了。
相关阅读
我已经劝进了微博敏感词updating (转载)河南省交通厅5任厅长的打炮史！ (转载)康特检查《厉害了，我的国》观影通知 (转载)红歌赏鉴：要嫁就嫁习大大这样的人 (转载)习主席可以去靖安登基了 (转载)搞个什么副业可以让你月入过万？愿你历尽千帆，归来仍是处男这位网友是买提翻墙回去的？谁能读懂这篇文章想表达什么意思？美中俄斗地主，就美国经常换人玩弯曲的软件公司从大到小， 从稳定的到startup 都用JIRA， SCRURe: 你们有没有感觉，没有了二娃 (转载)尼玛，老司机也要被禁了 (转载)这人自杀事先打麻药了吧？我得了长假综合症站错队是要丢命的你们说孙政才每天养情妇、拜龙袍哥是不信的 (转载)推背图第四十七象!! (转载)