s********i
发帖数: 891 | 1 那当然
所有已知的质数的乘积，再加上一。
这个数字要么是个质数，那肯定比所有已知的质数大。
这个数字要么不是质数，那肯定有质数比已知质数大，成为这个数字的因子。因为已知
质数都不是他的因子。
这个证明方法，只是为了证明质数没有上界而已。
既不知道这个造出的数是不是质数，也不知道万一这个数不是质数，他的因子怎么找。
除了脑体操之外，没别的用。
当然，我也不知道找个那么大的质数，就算找到了，有啥用。我觉得这个就像算PAI的
小数点后第一万亿位的数字精度一样，估计没啥实用价值。 |
|
h****2
发帖数: 8042 | 2 “质数只能被一和它自身整除。在自然数的无穷序列中，它们处于自己的位置上，和其
他所有数字一样，被前后两个数字挤着，但它们彼此间的距离却比其他数字更远一步。
它们是多疑而又孤独的数字”
“在质数当中还有一些更加特别的成员，数学家称之为“孪生质数”，它们是离得很近
的一对质数，几乎是彼此相邻。在他们之间只有一个偶数，阻隔了它们真正的亲密结束
，比如十一和十三，十七和十九，四十一和四十三。假如你有耐心继续数下去，就会发
现这样的孪生质数会越来越难遇到，越来越长遇到的是那些孤独的质数，它们迷失在那
个纯粹由数字组成的寂静而又富于节奏的空间中。”
“此时，你会不安地预感到，到那里为止，那些孪生质数的出现只是一种偶然，而孤独
才注定是它们真正的宿命。然后，当你正准备放弃的时候。。。。”
不抄了，推荐下这本书，还不错。八零后粒子物理学博士写的小说，意大利最高文学奖
的最年轻得主。 |
|
b****g
发帖数: 23 | 3 最近听了一个讲座，谈到factoring的问题，感觉很有趣，但还有很多不明白之处。
比如说，现在有些专业公司做数据加密，其核心就是使用了一把数字锁，这个数字是两
个非常大的质数的乘积。如果想破解这把锁，必须要把这两个质数找出来，也就是一个
facotring的过程。
我的问题是:
(1) 如果这种加密方法被普遍采用的话。那么加密的函数本身是怎么设计的？既然
factoring被认为是解密的核心部分，这个函数本身也是一个秘密吗？解密又从哪里下
手呢？
(2) 请问所有已知的质数是人类共享资源吗？比如说是否存在一个可以下载的数据库。
(3) 新质数是如何寻找和扩展的呢？看了网上关于“最大质数”的报导，比如 43rd
Mersenne Prime 已经找到。那么 43rd Mersenne Prime 与 42nd Mersenne Prime 之
间的数字有人考察么。学术届找下一个质数的时候是否要做遍历呢？
现在还没搞清楚解密的难度和工作量到底是体现在完善质数数据库还是在海量查找上。
有什么相关文章推荐么。多谢指教！ |
|
b****g
发帖数: 23 | 4 最近听了一个讲座，谈到factoring的问题，感觉很有趣，但还有很多不明白之处。
比如说，现在有些专业公司做数据加密，其核心就是使用了一把数字锁，这个数字是两
个非常大的质数的乘积。如果想破解这把锁，必须要把这两个质数找出来，也就是一个
facotring的过程。
我的问题是:
(1) 如果这种加密方法被普遍采用的话。那么加密的函数本身是怎么设计的？既然
factoring被认为是解密的核心部分，这个函数本身也是一个秘密吗？解密又从哪里下
手呢？
(2) 请问所有已知的质数是人类共享资源吗？比如说是否存在一个可以下载的数据库。
(3) 新质数是如何寻找和扩展的呢？看了网上关于“最大质数”的报导，比如 43rd
Mersenne Prime 已经找到。那么 43rd Mersenne Prime 与 42nd Mersenne Prime 之
间的数字有人考察么。学术届找下一个质数的时候是否要做遍历呢？
现在还没搞清楚解密的难度和工作量到底是体现在完善质数数据库还是在海量查找上。
有什么相关文章推荐么。多谢指教！ |
|
h****a
发帖数: 580 | 5 http://news.bbc.co.uk/chinese/simp/hi/default.stm
美国加利福尼亚州州立大学洛杉矶分校(UCLA)的一组数学家发现最新质数，可能赢得得
10万美元奖金。
所谓质数或称素数，就是一个正整数，除本身和 1 以外并没有任何其他因子。例如 2
、3、5、7 均是质数，而 4、6、8、9则不是；后者称为合成数或合数。
从这个观点可将整数分为两种，一种叫质数，一种叫合成数。
美国加州大学这组学者发现的最新质数据说是一个1300万位的数字。学者们通过将75台
电脑联机运算，找到了这个新质数。
据悉，数学家有人悬赏10万美金寻找第一个1000万数位以上的质数，因此这些加州大学
的学人弄不好可以因为自己的发现而得到一些实际的好处。 |
|
t******l
发帖数: 10908 | 6 举个例子就是一般的根号数是无限不循环小数的证明。。。因为质数分解唯一性，而且
质数也没法被消灭掉。。。导致被根号的有理数，可以把分子分母写成唯一的质数乘积
的形式，而且分子和分母没有相同的质数。而这样的情况下，如果有任何一个质数出现
的次数，不是根号次数的整数倍的话，这样根号的结果不可能写成一个分数。。。而这
导致该根号的结果不能写成一个有循环 pattern 的小数。
也就是说，因为质数的存在，导致把数从一种形式转化为另一种形式时（这里是把根号
数的形式转化为十进制小数的形式），会发生看不到任何重复的 pattern，但实际上
pattern 还是存在（是个根号数而不是随机乱码发生器）。。。这就告诉了地球智人，
在地球智人（猴子的某个变种），在表面上看不到任何重复 pattern 的时候，其底下
看不见的内在机制可能还是存在简单直接还给力的 pattern 的。。。而这让地球智人
的数学智商情何以堪。。。 |
|
w********e
发帖数: 297 | 7 所有质数的乘积+1也是质数
也是错的。
检查一个数是不是质数，要检查到那个数是不是它的平方根以下所有质数的倍数。
所有质数的乘积+1的平方根要远大于因子中最大的质数。 |
|
t******l
发帖数: 10908 | 8 因为我们人耳对比如纯四纯五和谐性的感觉，本质是基于绝对频率 2/3 这种两个小质
数构成的分数。
但问题是巴赫古诺肖邦柴可夫司机等等古人把小质数都用完了，剩下的后人再要标新立
异，只能用大质数了。
但大质数实在是刺耳不和谐。。。当然还好有卡拉OK版一大堆五音不全的，不和谐也无
所谓了。。。所以就有了现代音乐，本质上就是大质数分数。
当然还有一条路，就是玩音色。。。而人声是最丰富的音色，所以 pop music 就开始
以主唱为特色。 |
|
t******g
发帖数: 10390 | 9 不是说所有质数的乘积+1也是质数.
就是不知道人类知道的最大质数之前漏掉了多少质数. |
|
T****t
发帖数: 11162 | 10 只有周期蝉才相距质数年出现的。 周期是质数，不是年份是质数。
宇宙和素数又有什么关系？ |
|
b***y
发帖数: 14281 | 11 同意。没有定义乘法之前质数没有意义。而乘法只是加法的一种速记方式，理论上不是
必须的，有加法就可以了。所以质数这个概念完全是人为制造出来的。当然，一旦制造
出这个概念，立刻顺带制造出无穷多数论难题。但这不是揭示任何自然界的奥秘，其实
只是揭示了人类思维能力的内在缺陷。
数论里面基本上所有难题都是把质数和加法问题结合起来弄出来的，比方哥德巴赫猜想
。有个日本奇葩大牛数学家，自创了一套数学概念，从头搞起，直接先定义乘法，把乘
变成基础，然后就号称轻松解决很多数论难题，但是他这套体系太奇葩，到现在没多少
人懂，也不确定他的证明是不是真的有用。 |
|
n******g
发帖数: 17225 | 12 那人叫望月新一。
猜想叫ABC猜想
: 同意。没有定义乘法之前质数没有意义。而乘法只是加法的一种速记方式，理论
上不是
: 必须的，有加法就可以了。所以质数这个概念完全是人为制造出来的。当然，一
旦制造
: 出这个概念，立刻顺带制造出无穷多数论难题。但这不是揭示任何自然界的奥秘
，其实
: 只是揭示了人类思维能力的内在缺陷。
: 数论里面基本上所有难题都是把质数和加法问题结合起来弄出来的，比方哥德巴
赫猜想
: 。有个日本奇葩大牛数学家，自创了一套数学概念，从头搞起，直接先定义乘法
，把乘
: 变成基础，然后就号称轻松解决很多数论难题，但是他这套体系太奇葩，到现在
没多少
: 人懂，也不确定他的证明是不是真的有用。
|
|
g*********e
发帖数: 14401 | 13 第二个，假设n是质数，那么所有n的倍数都不是质数。
维护一个array，从1开始数，找到一个质数就把所有它的倍数都标为合数。这样速度比
较快。不过要估计array大小 |
|
A***o
发帖数: 358 | 14 如果允许漏掉一些质数，效率上可以做得比筛子法好很多，比如在第n个prime gap用
miller rabin找第一个质数作为第n个质数 |
|
n********h
发帖数: 13135 | 15 晚上吃饭，娃一边吃一边说，5只有除1和它自己的时候没有余数，除其他的数，都有余
数。我回答说：“太对了。这种除了1和自己，除其他的数有余数的，叫住质数”。娃
听了，发挥了一下，说3也是质数。我再追了一句，7是不是，娃说是。 然后我问娃，
偶数是不是质数。 娃说不是，因为所有的偶数除2没有余数。我说，有个偶数是例外，
知不知道是哪个。娃表示压力大，不知道。后来告诉娃2是个例外，娃很是开心。 |
|
z***o
发帖数: 2104 | 16 噗嗤
咣当
孤独的质数一把扯掉伪装的偶数头上的假发
“小样，你以为定个波浪卷，我就真以为你是泡面么？！”
#￥……—
偶数奄奄一息，艰难地说了句话，蹬腿了
“前面那个质数花了大价钱让我来逗你开心的，没想到居然是我生命的代价~~~~”
最深处拿望远镜观望的腹黑质数抬抬眼镜，冷冷的镜片后面微微眯起的狭长眼中精光闪
现，
要不要自己出马搞定呢？ |
|
s*****e
发帖数: 16824 | 17 这个很容易啊，可以背下来，把200位以内质数全背下来就行了。反正大质数非常少的。 |
|
t******l
发帖数: 10908 | 18 这个说明我们的小学数学教育还是有问题的。
乘法确实是重复相加的速记，但这在理论上是绝对必须的。。。因为数学的本质是寻找
pattern，而 "重复" 不仅仅是最最基本的 pattern，而且有可能地球智人的 pattern
都是基于 "重复"。。。区别仅仅是父母版推妈只痴迷于没有结构的简单重复（所谓的好
习惯），所以推妈们就痛恨 AIME 里面基于各种数学结构上的非简单重复。。。扯远了。
从这个角度看，质数的意义是极其基本的，也就是自然界对 "重复" 的抵抗，或多或少。
或者更进一步，质数是反"重复"反 pattern 的最最基本的力量。也可以认为是自然对地
球智人的数学智商的蔑视。 |
|
t******l
发帖数: 10908 | 19 歌德巴赫猜想的坑爹之处。。。在于一般的质数理论总是要么跟组合理论结合使用，要
么跟余数理论同余循环结合使用，或者 both。
但歌德巴赫猜想说，你还可以直接在同余循环和组合理论根本不存在的情况下，直接就
拿两个质数加起来，还能完备地产生自然数（当然是偶数，不过这个 trivial，除以二
就是自然数集合）。。。然后地球人里那些 so-called 数学家们（本质上还是猴子兼
职的我想），就集体 pass-out 这么多年也缓不过来。。。 |
|
C****o
发帖数: 1549 | 20 周期蝉的生命周期为17和13，是演化的结果。科学家普遍认为的原因是，首先这两个周
期都很长，因为周期蝉出现于距今180万年前，那是北美气温低，有时会遇到冷夏，成
年蝉需要高温，因此长生命周期可以提高成活率。其次这两个周期都是质数，这样可以
避开自己的天敌。如果不是质数，那么就有更多机会和自己天敌的生命周期相重叠。[6] |
|
|
w****o
发帖数: 2260 | 22 1. 如何判断一个数是不是质数？
2. 如何求第n个(nth)质数？
对于上面的两道题，有什么快的算法和实现？
谢谢！ |
|
s********u
发帖数: 1109 | 23 发现careercup上面面经的解答真是不忍直视，挺明了的思路经常有人写一长串代码，
乍看容易把人吓到。
我的思路是建立一个list存质数，然后对每个奇数检验(遍历一遍这个质数list），直
到这个list的size到N。
因为是经典题，所以想问问是否这个就是最优解法了。
list findNthPrime( int N ){
int prime = 2;
int num = 3;
list primes;
primes.push_back(2);
while( primes.size() < n){
for( list::iterator it = primes.begin(); it != primes.end() &&
*it <= (int) sqrt( num ); it++ ){
if( num%(*it) == 0 ){
num += 2;
it = prime... 阅读全帖 |
|
t****e
发帖数: 205 | 24 貌似越大质数越稀疏，是这样的么？质数的密度是怎么个衰减法？指数？密度的
fluctuaion呢？跟密度有什么关系？正比？平方根？ |
|
S***p
发帖数: 19902 | 25 有个老师门口贴了几页纸，密密麻麻的数字，是一个质数
据说已知最大的质数有４亿位 |
|
n****4
发帖数: 12553 | 26 把最大的质数放到2的指数上，结果再减一，又是个更大的质数 |
|
n***d
发帖数: 8857 | 27 我查了下，有个假说是宇宙由数学组成，mathematical university hypothesis 。数
学不再是描述，而是实体。 而且质数真的这么重要吗？质数不能整除，但是可以除成
小数，小数也是确定的数。 |
|
H********g
发帖数: 43926 | 28 【 以下文字转载自 Military 讨论区 】
发信人: wugongpanda (Sela'ma ashal'anore!), 信区: Military
标 题: Re: 质数是不是最没用的数学概念
发信站: BBS 未名空间站 (Wed May 31 01:28:00 2017, 美东)
对付外星人入侵
如果天顶星人来地球，问你们知道的质数最大多少？ 一看比我们知道的少，自己就羞
愧的
逃跑了。 一看比我们多，那我们趁早投降，该当蚂蚁当蚂蚁，该献菊花献菊花。 |
|
a*f
发帖数: 1790 | 29 re
找到一个质数放到hashtable里面，只检查是否被里面的质数群整除 |
|
发帖数: 1 | 30 有一个有限域GF(p)，p为一个很大的质数。
一个定义在GF(p)上的多项式，项数为n，n可能为质数。
GF(p)中不一定含有n-th root of unity。
如何对这个多项式进行FFT？ |
|
h**********c
发帖数: 4120 | 31 Study 曲线 sin（a * \pi / x)， at 1+ derivative >0, at a- derivative <0.
sin（a * \pi / x) 于 x 轴没有交点， a 为质数，如a 为合数， 则与 x 轴有交点。
除非相交于sqrt(a)， 交点也就是根成对出现。
如果a 是恰恰两个质数的乘积，则只有两个交点，观察曲线如何穿越 x轴，我们发现
sin（a * \pi / x) 在 x = sqrt （a）小于零。 在 （1， sqrt（a)) ，sin（a * \
pi / x) 有两部分，一部分大于零，零一部小于零。因此，可以用binary search 搜索
。 开销 O(log(a)).
对于所有的sin（a * \pi / x) 在 x = sqrt （a）小于零情况，对binary search 进
行改进，也可以搜索到a 的一个因子，因为 在x= 1 函数大于零， 在x= sqrt (a) 小
于零。开销 O(log(a)).
对于sin（a * \pi / x) 在 x = sqrt （a）大于零情况，如有因子必在 （1，a^{1/4}
)... 阅读全帖 |
|
c******n
发帖数: 380 | 32 判断一个数n是不是质数，按照定义要看除以从2到n-1的余数都不是0，实际上只要看从
2到小于等于n的平方根的最大质数的余数就可以了，请问该如何证明呢？ |
|
s*****V
发帖数: 21731 | 33 【 以下文字转载自 Military 讨论区 】
发信人: saturnV (土星五号), 信区: Military
标 题: 日本数学家望月新一宣称证明质数之间深层联系猜想——abc猜想
发信站: BBS 未名空间站 (Sun Oct 21 16:13:23 2012, 美东)
据《自然》网站报道，一向平静的数学界近日兴奋起来，一位日本数学家宣称解决了数
论中最重要的问题之一。
日本京都大学数理解析研究所教授望月新一（Shinichi Mochizuki，1969年3月29日—
—）发表了一篇500页的论文(PDF)，声称证明了有近三十年历史的abc猜想（abc
conjecture）。
abc猜想于1985年由David Masser和Joseph Oesterle分别独立提出。与费马大定理（
Fermat’s Last Theorem）相比较，abc猜想可能没有那么出名，但在某些方面它更为
重要。abc猜想涉及到质数、加法和乘法之间的关系，如果证明正确，将有可能在数论
领域掀起一场革命，将能大大简化费马大定理的证明。
UCLA数学家陶哲轩和牛津大学数学家Minhyong Kim... 阅读全帖 |
|
t*******a
发帖数: 210 | 34 我记得原因是质数年不容易被捕食者追纵。
说采取这种办法的生物，多半是出现的时候，没什么抵抗力。所以对策就是
一是不经常出现，而且质数年出现17年突然大批出现一次，捕食动物措手不及，拼命去
吃也吃不完，所以好歹能剩下一批。而且因为这种年限循环，捕食动物很难跟踪，
不容易掌握规律，无法按时产生大量幼子去吃。好像竹子也采用的这种方法。 |
|
b*******8
发帖数: 37364 | 35 随便给个一百位数，稍加思考就判断是否质数。
比四则运算乘方开方牛多了 |
|
|
l****p
发帖数: 27354 | 37 那你试验一下，1到7这7个数，有多种排列，请找出一个质数。 |
|
|
|
k**********4
发帖数: 16092 | 40 禅总是在质数年份出现，现在至少知道禅最晚能在哪一年出现 |
|
|
w*********a
发帖数: 9279 | 42 对付外星人入侵
如果天顶星人来地球，问你们知道的质数最大多少？ 一看比我们知道的少，自己就羞
愧的
逃跑了。 一看比我们多，那我们趁早投降，该当蚂蚁当蚂蚁，该献菊花献菊花。 |
|
w*********a
发帖数: 9279 | 43 其他科学，数学都是有假设的。
只有质数是普遍存在的真理，也只有这个才是我们和外星人，和上帝交流的途径。 |
|
|
D***r
发帖数: 7511 | 45 连蝉的生命周期都是质数。有17年，13年，11年等等 |
|
|
b*******8
发帖数: 37364 | 47 阿发狗证明人类研究围棋几千年都不得要领。
宇宙比围棋复杂不知道多少数量级，等外星人坐飞船出现了，不要惊讶，人家的科学体
系跟我们完全不一样，质数算个屁啊，还以为人家在乎。非洲部落跳大神的，还觉得自
己手里的大神是宇宙通用语言呢，见到西方殖民者就拿出来显摆。 |
|
F*********s
发帖数: 223 | 48 哥德巴赫猜想说的很清楚，质数是数的building block. |
|
b*******8
发帖数: 37364 | 49 质数本来是用来做乘法基础的，哥德巴赫非拿来做加法基础，结果折腾了无数地球数学
家！好比鸡巴是用来直插的，他非要把鸡巴拧成一个环，用来绑东西。 |
|
F*********s
发帖数: 223 | 50 加显然比乘更基础。其实哥德巴赫猜想是说，自然数有质数就够了，其他的数都是像几
何里的辅助线一样，帮助你有限的智力好理解一点。 |
|
