由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 关于质数(prime number)的算法题
相关主题
问道题: prime factor问个算法题
经典题:找前N个质数find Kth Largest Element 有没有更简化的解法
一道电面题G家onsite 随机数一题
一道算法题目用java面试真吃亏
details 2nd smallest element in an arrayGoogle电话面试题目
leetcode上遇到的问题a problem from leetcode: high efficiency algorithm for combinations problem
说一下上周五狗狗家的面试另外求祝福combinations 有没有 iterative的方法阿 ?
CS: print all combination from an array今天刚跪Amazon,伤心之余提着伤疤来发个面经,随便跪求各路大神refer
相关话题的讨论汇总
话题: 质数话题: int话题: arraylist话题: prime话题: primes
1 (共1页)
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,知道的话应该能加分
相关主题
leetcode上遇到的问题问个算法题
说一下上周五狗狗家的面试另外求祝福find Kth Largest Element 有没有更简化的解法
CS: print all combination from an arrayG家onsite 随机数一题
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,你取范围的大小为多少?

相关主题
用java面试真吃亏combinations 有没有 iterative的方法阿 ?
Google电话面试题目今天刚跪Amazon,伤心之余提着伤疤来发个面经,随便跪求各路大神refer
a problem from leetcode: high efficiency algorithm for combinations problem问个递归的问题
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把所有的都存起来,需要第几个,直接去取好
: 了。

1 (共1页)
相关主题
今天刚跪Amazon,伤心之余提着伤疤来发个面经,随便跪求各路大神referdetails 2nd smallest element in an array
问个递归的问题leetcode上遇到的问题
求点评:电话面试(今天第二天没有消息回复,感觉可能挂了)说一下上周五狗狗家的面试另外求祝福
[合集] Google电话面试题目CS: print all combination from an array
问道题: prime factor问个算法题
经典题:找前N个质数find Kth Largest Element 有没有更简化的解法
一道电面题G家onsite 随机数一题
一道算法题目用java面试真吃亏
相关话题的讨论汇总
话题: 质数话题: int话题: arraylist话题: prime话题: primes