w****o
发帖数: 2260 | 1 1. 如何判断一个数是不是质数？
2. 如何求第n个(nth)质数？
对于上面的两道题，有什么快的算法和实现？
谢谢！ |
S*******w
发帖数: 24236 | 2 第一个是看能不能被1 到 sqrt（num）的数整除？
【在 w****o 的大作中提到】
: 1. 如何判断一个数是不是质数？
: 2. 如何求第n个(nth)质数？
: 对于上面的两道题，有什么快的算法和实现？
: 谢谢！
|
g*********e
发帖数: 14401 | 3 第二个，假设n是质数，那么所有n的倍数都不是质数。
维护一个array，从1开始数，找到一个质数就把所有它的倍数都标为合数。这样速度比
较快。不过要估计array大小 |
w**z
发帖数: 8232 | 4 好像只要看能否被质数整除就行了吧。
如果不能被2，整除，那也不可能被4， 6， 8。。。整除。
上次面试，就栽这山了。
【在 S*******w 的大作中提到】
: 第一个是看能不能被1 到 sqrt（num）的数整除？
|
S*******w
发帖数: 24236 | 5 嗯 不过怎么判断啊
【在 w**z 的大作中提到】
: 好像只要看能否被质数整除就行了吧。
: 如果不能被2，整除，那也不可能被4， 6， 8。。。整除。
: 上次面试，就栽这山了。
|
w**z
发帖数: 8232 | 6 搞个Array, 把以知的质数都存起来。就象第二题那样的解法。只是Array只能到一定大，总有超过的时候。
【在 S*******w 的大作中提到】
: 嗯 不过怎么判断啊
|
C******a
发帖数: 33 | 7 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)质数？
: 对于上面的两道题，有什么快的算法和实现？
: 谢谢！
|
n**0
发帖数: 136 | 8 这里有比较详细的讨论
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=
【在 w****o 的大作中提到】
: 1. 如何判断一个数是不是质数？
: 2. 如何求第n个(nth)质数？
: 对于上面的两道题，有什么快的算法和实现？
: 谢谢！
|
e***l
发帖数: 710 | 9 还有高级一点的随机算法，Miller-Rabin，知道的话应该能加分 |
w**z
发帖数: 8232 | 10 只有学数学的才会知道这个吧。估计面你的都不一定会知道。
【在 e***l 的大作中提到】
: 还有高级一点的随机算法，Miller-Rabin，知道的话应该能加分
|
|
|
S*******w
发帖数: 24236 | 11 搞密码的都懂
【在 w**z 的大作中提到】
: 只有学数学的才会知道这个吧。估计面你的都不一定会知道。
|
w**z
发帖数: 8232 | 12 俺只会用BASE64，哈哈
【在 S*******w 的大作中提到】
: 搞密码的都懂
|
H***e
发帖数: 476 | 13 对第二题，
如果用消除prime的倍数的方法，如何一开始确定array的size呢
如果说n=1000,你取范围的大小为多少？
【在 w****o 的大作中提到】
: 1. 如何判断一个数是不是质数？
: 2. 如何求第n个(nth)质数？
: 对于上面的两道题，有什么快的算法和实现？
: 谢谢！
|
p*****2
发帖数: 21240 | 14
用ArrayList不就行了？
【在 H***e 的大作中提到】
: 对第二题，
: 如果用消除prime的倍数的方法，如何一开始确定array的size呢
: 如果说n=1000,你取范围的大小为多少？
|
H***e
发帖数: 476 | 15 不是
你可能没明白我的意思
比如你要求第1000的质数
你初始的测试范围是1到多少？10000? 20000?
如果太小，导致不够，就还得扩展，然后把扩展的数一个一个的看能不能被前面的质素
整除，有点麻烦
【在 p*****2 的大作中提到】
:
: 用ArrayList不就行了？
|
p*****2
发帖数: 21240 | 16 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+" ");
} |
p*****2
发帖数: 21240 | 17
看我代码行不行。
【在 H***e 的大作中提到】
: 不是
: 你可能没明白我的意思
: 比如你要求第1000的质数
: 你初始的测试范围是1到多少？10000? 20000?
: 如果太小，导致不够，就还得扩展，然后把扩展的数一个一个的看能不能被前面的质素
: 整除，有点麻烦
|
H***e
发帖数: 476 | 18 几个优化：
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
if(i%primes.get(j)==0)
break;
if(j==primes.size())
primes.add(i);
if(primes.size()==n)
break;
}
for(int i:primes)
System.out.print(i+" ");
} |
p*****2
发帖数: 21240 | 19
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 primes=new ArrayList();
: int n=100;
|
p*****2
发帖数: 21240 | 20
我明白你的意思了。上边有人提到消除倍数的方法。这个方法不一定实用吧？
【在 H***e 的大作中提到】
: 对第二题，
: 如果用消除prime的倍数的方法，如何一开始确定array的size呢
: 如果说n=1000,你取范围的大小为多少？
|
|
|
H***e
发帖数: 476 | 21 大啊。
你用一个array保存flag，如果已经被划掉了，根本不用再做 % 运算了，省了很多计算
【在 p*****2 的大作中提到】
:
: 我明白你的意思了。上边有人提到消除倍数的方法。这个方法不一定实用吧？
|
p*****2
发帖数: 21240 | 22
我做题的时候基本这样就可以了。你说的这个是用空间换时间，但是就是你说的那个问
题好像没法解决。
【在 H***e 的大作中提到】
: 大啊。
: 你用一个array保存flag，如果已经被划掉了，根本不用再做 % 运算了，省了很多计算
|
l*****a
发帖数: 14598 | 23 得面试官认为可以才可以
【在 p*****2 的大作中提到】
:
: 我做题的时候基本这样就可以了。你说的这个是用空间换时间，但是就是你说的那个问
: 题好像没法解决。
|
p*****2
发帖数: 21240 | 24
很多时候你也不知道面试官认可不认可，除非最后拿到offer。呵呵。
【在 l*****a 的大作中提到】
: 得面试官认为可以才可以
|
l*****a
发帖数: 14598 | 25 比方说对于3，6,9,12,15,18,21,27。。。...已经是非质数，下次就不用判断9,15,21,27等
的倍数了
bool flag[]=new bool[n];
for(int i=0;i
for(i=2;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
发帖数: 14598 | 26 其实，拿到offer也不见得你所有题都答对了
不过是人家认可了你的能力。。。
【在 p*****2 的大作中提到】
:
: 很多时候你也不知道面试官认可不认可，除非最后拿到offer。呵呵。
|
p*****2
发帖数: 21240 | 27
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: for(i=2;i: {
: if(flag[i]==false) continue;
: k=2;
: while(i*k: {
|
l*****a
发帖数: 14598 | 28 对，就是说用这个办法不太好确定初始大小。
或许只能用你的办法，动态追加。但中间的处理确实不如那个优化。
所以还要再思考
【在 p*****2 的大作中提到】
:
: 21,27等
: 你这个也没有解决那个问题吧？就是如何定义n的问题。
|
f*******l
发帖数: 66 | 29 这里有一个解法
http://primes.utm.edu/nthprime/algorithm.php
如今所知的质数有限，应该直接用table把所有的都存起来，需要第几个，直接去取好
了。
【在 l*****a 的大作中提到】
: 对，就是说用这个办法不太好确定初始大小。
: 或许只能用你的办法，动态追加。但中间的处理确实不如那个优化。
: 所以还要再思考
|
m*******l
发帖数: 12782 | 30 质数是无限的
【在 f*******l 的大作中提到】
: 这里有一个解法
: http://primes.utm.edu/nthprime/algorithm.php
: 如今所知的质数有限，应该直接用table把所有的都存起来，需要第几个，直接去取好
: 了。
|
