y***n
发帖数: 1594 | 1 好像interview是个比较popular的问题，大家一般怎么回答？ |
t****t
发帖数: 6806 | 2 这种问题google一下就可以了...
【在 y***n 的大作中提到】
: 好像interview是个比较popular的问题，大家一般怎么回答？
|
y***n
发帖数: 1594 | 3 google 了一些。
wikipedia 有个比较好的终结，我不知道大家一般如何回答比较好。对方的
expectation 一般是什么。
谢谢。 |
t****t
发帖数: 6806 | 4 一般随机的大数就费马测试就可以了. 小数字随便怎么搞都好.
如果要证明就很困难.
【在 y***n 的大作中提到】
: google 了一些。
: wikipedia 有个比较好的终结，我不知道大家一般如何回答比较好。对方的
: expectation 一般是什么。
: 谢谢。
|
O*******d
发帖数: 20343 | 5 我在interview时被问过这个问题。 对方就是想了解你的解决问题的能力。 我不记得
理论，就马上写了一个循环。 如
果数是1或2，就是prime，其他数只看奇数。用brute force 看除法的余数是否为零。
但是要声明这个方法的适用范
围。
【在 y***n 的大作中提到】
: google 了一些。
: wikipedia 有个比较好的终结，我不知道大家一般如何回答比较好。对方的
: expectation 一般是什么。
: 谢谢。
|
y***n
发帖数: 1594 | |
r****t
发帖数: 10904 | 7 问没有准备的人还是很能看出高低的，都准备过了的人自然是觉得无聊了。
【在 y***n 的大作中提到】
: 有时候觉得这种问题挺无聊的。
|
p***o
发帖数: 1252 | 8 这能看出啥，不懂伪素数判别的还能当场想出这个方法？更别说那个P的算法了。
【在 r****t 的大作中提到】
: 问没有准备的人还是很能看出高低的，都准备过了的人自然是觉得无聊了。
|
h*******e
发帖数: 225 | 9 能看出你知道多少，程序写得怎么样，对系统结构了解多少等等。
能问的问题多了去了，focus又不一定只是算法。
【在 p***o 的大作中提到】
: 这能看出啥，不懂伪素数判别的还能当场想出这个方法？更别说那个P的算法了。
|
r****t
发帖数: 10904 | 10 is 费马测试 sometimes giving out wrong answer?
【在 t****t 的大作中提到】
: 一般随机的大数就费马测试就可以了. 小数字随便怎么搞都好.
: 如果要证明就很困难.
|
t****t
发帖数: 6806 | 11 本来就没说是100%正确. 但是错误的概率不大.
实用中这个测试叫miller-rabin, 做了一定的简化, 但是准确度是相当高的. 用这个方
法做初步的筛选, 然后再用更复杂的方法确认.
对于大质数, 没人会用找因子的方法来测试质数的, 质因数分解目前来说, 本来就没什
么好办法. 这个事实也是目前RSA的理论基础. 如果质因数随便就分解了, 那RSA就完全
没用了.
EDIT: 刚查了查教科书, 记错了. miller-rabin比费马测试准确多了. 虽然它还是一定程度上基于费马小定理, 但是它能保证对于任意的合数, 至少有3/4的底数可以用于发现合数(实际上这个比例要大得多). 对于carmicheal number, 费马测试则一定会失败.
【在 r****t 的大作中提到】
: is 费马测试 sometimes giving out wrong answer?
|
