请问什么是质数与合数？什么是奇数与偶数呢？麻烦详细讲一下？ - 知乎
请问什么是质数与合数？什么是奇数与偶数呢？麻烦详细讲一下？ - 知乎首页知乎知学堂发现等你来答切换模式登录/注册数学数论数学证明请问什么是质数与合数？什么是奇数与偶数呢？麻烦详细讲一下？关注者3被浏览1,093关注问题写回答邀请回答好问题添加评论分享2 个回答默认排序雪珂随笔数学家 关注质数也称素数，指的是只能被1和其自身整除的正整数；合数，是若干个（至少2个）素数的乘积，其中包括至少1个大于1的正因子。能被2 整除的自然数为偶数，可表示为2n。不能被2整除的正整数为奇数，可表示为2n+1。发布于 2022-12-06 20:33赞同添加评论分享收藏喜欢收起wyl2928喜爱数字游戏 关注先说说奇数、偶数：奇数即通常所说的“单数”，像1，3，5，7，9……偶数即通常说的“双数”，像0，2，4，6，8……所谓奇、偶也就是单、双。再说质数和合数，质数与合数是相对而言。质数：一个数除了1和本身外，不被任何其他数整除，这个数就是质数；如2，3，5，7，11，13……一个数除了1和本身外，还可以被其他数整除，那么这个数是合数。像4，6，8，9，15，21，25，77……发布于 2023-08-22 15:48赞同 1添加评论分享收藏喜欢收起
请问什么是质数与合数？什么是奇数与偶数呢？麻烦详细讲一下？ - 知乎
请问什么是质数与合数？什么是奇数与偶数呢？麻烦详细讲一下？ - 知乎首页知乎知学堂发现等你来答切换模式登录/注册数学数论数学证明请问什么是质数与合数？什么是奇数与偶数呢？麻烦详细讲一下？关注者3被浏览1,093关注问题写回答邀请回答好问题添加评论分享2 个回答默认排序雪珂随笔数学家 关注质数也称素数，指的是只能被1和其自身整除的正整数；合数，是若干个（至少2个）素数的乘积，其中包括至少1个大于1的正因子。能被2 整除的自然数为偶数，可表示为2n。不能被2整除的正整数为奇数，可表示为2n+1。发布于 2022-12-06 20:33赞同添加评论分享收藏喜欢收起wyl2928喜爱数字游戏 关注先说说奇数、偶数：奇数即通常所说的“单数”，像1，3，5，7，9……偶数即通常说的“双数”，像0，2，4，6，8……所谓奇、偶也就是单、双。再说质数和合数，质数与合数是相对而言。质数：一个数除了1和本身外，不被任何其他数整除，这个数就是质数；如2，3，5，7，11，13……一个数除了1和本身外，还可以被其他数整除，那么这个数是合数。像4，6，8，9，15，21，25，77……发布于 2023-08-22 15:48赞同 1添加评论分享收藏喜欢收起
质数 - 维基百科，自由的百科全书
质数 - 维基百科，自由的百科全书
跳转到内容
主菜单
主菜单
移至侧栏
隐藏
导航
首页分类索引特色内容新闻动态最近更改随机条目资助维基百科
帮助
帮助维基社群方针与指引互助客栈知识问答字词转换IRC即时聊天联络我们关于维基百科
搜索
搜索
创建账号
登录
个人工具
创建账号 登录
未登录编辑者的页面 了解详情
贡献讨论
目录
移至侧栏
隐藏
序言
1定义和例子
2算术基本定理
开关算术基本定理子章节
2.11是否为质数
3历史
4素数的数目
开关素数的数目子章节
4.1欧几里得的证明
4.2欧拉的解析证明
5测试质数与整数分解
开关测试质数与整数分解子章节
5.1试除法
5.2筛法
5.3质数测试与质数证明
5.4专用目的演算法与最大已知质数
5.5整数分解
6质数分布
开关质数分布子章节
6.1质数的公式
6.2一特定数以下的质数之数量
6.3等差数列
6.4二次多项式的质数值
7未解决的问题
开关未解决的问题子章节
7.1ζ函数与黎曼猜想
7.2其他猜想
8应用
开关应用子章节
8.1模一质数与有限体之运算
8.2其他数学里出现的质数
8.3公开金钥加密
8.4自然里的质数
9推广
开关推广子章节
9.1环内的素元
9.2质理想
9.3赋值
10在艺术与文学里
11另见
12注记
13参考资料
14外部链接
开关外部链接子章节
14.1质数产生器与计算器
开关目录
质数
136种语言
AfrikaansAlemannischAragonésÆngliscالعربيةالدارجةمصرىঅসমীয়াAsturianuAzərbaycancaتۆرکجهБашҡортсаŽemaitėškaБеларускаяБеларуская (тарашкевіца)БългарскиবাংলাBrezhonegBosanskiCatalàکوردیČeštinaЧӑвашлаCymraegDanskDeutschZazakiΕλληνικάEmiliàn e rumagnòlEnglishEsperantoEspañolEestiEuskaraفارسیSuomiVõroNa Vosa VakavitiFøroysktFrançaisNordfriiskGaeilge贛語Kriyòl gwiyannenGalegoગુજરાતીHawaiʻiעבריתहिन्दीHrvatskiHornjoserbsceKreyòl ayisyenMagyarՀայերենԱրեւմտահայերէնInterlinguaBahasa IndonesiaÍslenskaItaliano日本語PatoisLa .lojban.JawaქართულიҚазақшаភាសាខ្មែរಕನ್ನಡ한국어KurdîKernowekКыргызчаLatinaLëtzebuergeschLimburgsLombardLietuviųLatviešuМакедонскиമലയാളംМонголमराठीBahasa MelayuMaltiမြန်မာဘာသာPlattdüütschनेपालीNederlandsNorsk nynorskNorsk bokmålOccitanଓଡ଼ିଆਪੰਜਾਬੀPolskiPiemontèisپنجابیPortuguêsRomânăРусскийСаха тылаSicilianuSrpskohrvatski / српскохрватскиTaclḥitසිංහලSimple EnglishSlovenčinaSlovenščinaSoomaaligaShqipСрпски / srpskiSvenskaKiswahiliŚlůnskiதமிழ்తెలుగుТоҷикӣไทยTagalogTürkçeئۇيغۇرچە / UyghurcheУкраїнськаاردوOʻzbekcha / ўзбекчаVènetoVepsän kel’Tiếng ViệtWest-VlamsWalonWinaray吴语ХальмгייִדישYorùbáⵜⴰⵎⴰⵣⵉⵖⵜ ⵜⴰⵏⴰⵡⴰⵢⵜ文言Bân-lâm-gú粵語
编辑链接
条目讨论
简体
不转换简体繁體大陆简体香港繁體澳門繁體大马简体新加坡简体臺灣正體
阅读编辑查看历史
工具
工具
移至侧栏
隐藏
操作
阅读编辑查看历史
常规
链入页面相关更改上传文件特殊页面固定链接页面信息引用本页获取短URL下载二维码维基数据项目
打印/导出
下载为PDF可打印版
在其他项目中
维基共享资源
维基百科，自由的百科全书
各种各样的数
基本
N
⊆
Z
⊆
Q
⊆
R
⊆
C
{\displaystyle \mathbb {N} \subseteq \mathbb {Z} \subseteq \mathbb {Q} \subseteq \mathbb {R} \subseteq \mathbb {C} }
正数
R
+
{\displaystyle \mathbb {R} ^{+}}
自然数
N
{\displaystyle \mathbb {N} }
正整数
Z
+
{\displaystyle \mathbb {Z} ^{+}}
小数
有限小数
无限小数
循环小数
有理数
Q
{\displaystyle \mathbb {Q} }
代数数
A
{\displaystyle \mathbb {A} }
实数
R
{\displaystyle \mathbb {R} }
复数
C
{\displaystyle \mathbb {C} }
高斯整数
Z
[
i
]
{\displaystyle \mathbb {Z} [i]}
负数
R
−
{\displaystyle \mathbb {R} ^{-}}
整数
Z
{\displaystyle \mathbb {Z} }
负整数
Z
−
{\displaystyle \mathbb {Z} ^{-}}
分数
单位分数
二进分数
规矩数
无理数
超越数
虚数
I
{\displaystyle \mathbb {I} }
二次无理数
艾森斯坦整数
Z
[
ω
]
{\displaystyle \mathbb {Z} [\omega ]}
延伸
二元数
四元数
H
{\displaystyle \mathbb {H} }
八元数
O
{\displaystyle \mathbb {O} }
十六元数
S
{\displaystyle \mathbb {S} }
超实数
∗
R
{\displaystyle ^{*}\mathbb {R} }
大实数
上超实数
双曲复数
双复数
复四元数
共四元数（英语：Dual quaternion）
超复数
超数
超现实数
其他
质数
P
{\displaystyle \mathbb {P} }
可计算数
基数
阿列夫数
同馀
整数数列
公称值
规矩数
可定义数
序数
超限数
p进数
数学常数
圆周率
π
=
3.14159265
{\displaystyle \pi =3.14159265}
…
自然对数的底
e
=
2.718281828
{\displaystyle e=2.718281828}
…
虚数单位
i
=
−
1
{\displaystyle i={\sqrt {-{1}}}}
无限大
∞
{\displaystyle \infty }
查论编
质数（Prime number），又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。大于1的自然数若不是质数，则称之为合数（也称为合成数）。例如，5是个质数，因为其正因数只有1与5。7是个质数，因为其正因数只有1与7。而4则是个合数，因为除了1与4外，2也是其正因数。6也是个合数，因为除了1与6外，2与3也是其正因数。算术基本定理确立了质数于数论里的核心地位：任何大于1的整数均可被表示成一串唯一质数之乘积。为了确保该定理的唯一性，1被定义为不是质数，因为在因式分解中可以有任意多个1（如3、1×3、1×1×3等都是3的有效因数分解）。
古希腊数学家欧几里得于公元前300年前后证明有无限多个质数存在（欧几里得定理）。现时人们已发现多种验证质数的方法。其中试除法比较简单，但需时较长：设被测试的自然数为
n
{\displaystyle n}
，使用此方法者需逐一测试2与
n
{\displaystyle {\sqrt {n}}}
之间的质数，确保它们无一能整除
n
{\displaystyle n}
。对于较大或一些具特别形式（如梅森数）的自然数，人们通常使用较有效率的演算法测试其是否为质数（例如282589933-1是直至2018年12月为止已知最大的梅森质数[1]，也是直至2018年12月为止已知最大的质数）。虽然人们仍未发现可以完全区别质数与合数的公式，甚至研究质数分布时相当有力的筛法也会碰到奇偶性问题（也就是多种筛法都无法区别质数跟两个质数相乘的合数的问题），但已建构了质数的分布模式（亦即质数在大数时的统计模式）。19世纪晚期得到证明的质数定理指出：一个任意自然数n为质数的机率反比于其数位（或
n
{\displaystyle n}
的对数）。
许多有关质数的问题依然未解，如哥德巴赫猜想（每个大于2的偶数可表示成两个素数之和）及孪生质数猜想（存在无穷多对相差2的质数）。这些问题促进了数论各个分支的发展，主要在于数字的解析或代数方面。质数被用于资讯科技里的几个程序中，如公钥加密利用了难以将大数分解成其质因数之类的性质。质数亦在其他数学领域里形成了各种广义化的质数概念，主要出现在代数里，如质元素及质理想。
定义和例子[编辑]
一个自然数（如1、2、3、4、5、6等）若恰有两个正因数（1及此数本身），则称之为质数[2]。大于1的自然数若不是质数，则称之为合数。
数字12不是质数，因为将12以每4个分成1组，恰可分成3组（也有其他分法）。11则无法分成数量都大于1且都相同的各组，而都会有剩馀。因此，11为质数。
在数字1至6间，数字2、3与5为质数，1、4与6则不是质数。1不是质数，其理由见下文。2是质数，因为只有1与2可整除该数。接下来，3亦为质数，因为1与3可整除3，3除以2会馀1。因此，3为质数。不过，4是合数，因为2是另一个（除1与4外）可整除4的数：
4 = 2 · 2
5又是个质数：数字2、3与4均不能整除5。接下来，6会被2或3整除，因为
6 = 2 · 3
因此，6不是质数。右图显示12不是质数：12 = 3 · 4。不存在大于2的偶数为质数，因为依据定义，任何此类数字
n
{\displaystyle n}
均至少有三个不同的因数，即1、2与
n
{\displaystyle n}
。这意指
n
{\displaystyle n}
不是质数。因此，“奇质数”系指任何大于2的质数。类似地，当使用一般的十进位制时，所有大于5的质数，其尾数均为1、3、7或9，因为尾数0、2、4、6、8为2的倍数，尾数为0或5的数字为5的倍数。
若
n
{\displaystyle n}
为一自然数，则1与
n
{\displaystyle n}
会整除
n
{\displaystyle n}
。因此，质数的条件可重新叙述为：一个数字为质数，若该数大于1，且没有
2
,
3
,
…
,
n
−
1
{\displaystyle 2,3,\ldots ,n-1}
会整除
n
{\displaystyle n}
。另一种叙述方式为：一数
n
>
1
{\displaystyle n>1}
为质数，若不能写成两个整数
a
{\displaystyle a}
与
b
{\displaystyle b}
的乘积，其中这两数均大于1：
n
=
a
⋅
b
{\displaystyle n=a\cdot b}
.
换句话说，
n
{\displaystyle n}
为质数，若
n
{\displaystyle n}
无法分成数量都大于1且都相同的各组。
由所有质数组成之集合通常标记为P或
P
{\displaystyle \mathbb {P} }
。
前168个质数（所有小于1000的质数）为2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, ...（OEIS数列A000040）。
算术基本定理[编辑]
主条目：算术基本定理
质数对于数论与一般数学的重要性来自于“算术基本定理”。该定理指出，每个大于1的整数均可写成一个以上的质数之乘积，且除了质因数的排序不同外是唯一的[3]。质数可被认为是自然数的“基本建材”，例如：
23244
= 2 · 2 · 3 · 13 · 149
= 22 · 3 · 13 · 149. （22表示2的平方或2次方。）
如同此例一般，相同的因数可能出现多次。一个数n的分解：
n
=
p
1
⋅
p
2
⋅
…
⋅
p
t
{\displaystyle n=p_{1}\cdot p_{2}\cdot \ldots \cdot p_{t}}
成（有限多个）质因数
p
1
{\displaystyle p_{1}}
、
p
2
{\displaystyle p_{2}}
、……、
p
t
{\displaystyle p_{t}}
，称之为
n
{\displaystyle n}
的“因数分解”。算术基本定理可以重新叙述为，任一质数分解除了因数的排序外，都是唯一的。因此，尽管实务上存在许多质数分解演算法来分解较大的数字，但最后都会得到相同的结果。
若
p
{\displaystyle p}
为质数，且
p
{\displaystyle p}
可整除整数的乘积
a
b
{\displaystyle ab}
，则
p
{\displaystyle p}
可整除
a
{\displaystyle a}
或可整除
b
{\displaystyle b}
。此一命题被称为欧几里得引理[4]，被用来证明质数分解的唯一性。
1是否为质数[编辑]
最早期的希腊人甚至不将1视为是一个数字[5]，因此不会认为1是质数。到了中世纪与文艺复兴时期，许多数学家将1纳入作为第一个质数[6]。到18世纪中期，克里斯蒂安·哥德巴赫在他与李昂哈德·欧拉著名的通信里将1列为第一个质数，但欧拉不同意[7]。然而，到了19世纪，仍有许多数学家认为数字1是个质数。例如，德里克·诺曼·雷默（Derrick Norman Lehmer）在他那最大达10,006,721的质数列表[8]中，将1列为第1个质数[9]。昂利·勒贝格据说是最后一个称1为质数的职业数学家[10]。到了20世纪初，数学家开始认为1不是个质数，但反而作为“单位”此一特殊类别[6]。
许多数学成果在称1为质数时，仍将有效，但欧几里何的算术基本定理（如上所述）则无法不重新叙述而仍然成立。例如，数字15可分解成3 · 5及 1 · 3 · 5；若1被允许为一个质数，则这两个表示法将会被认为是将15分解至质数的不同方法，使得此一定理的陈述必须被修正。同样地，若将1视为质数，埃拉托斯特尼筛法将无法正常运作：若将1视为质数，此一筛法将会排除掉所有1的倍数（即所有其他的数），只留下数字1。此外，质数有几个1所没有的性质，如欧拉函数的对应值，以及除数函数的总和[11][12]。
历史[编辑]
埃拉托斯特尼筛法是个找出在一特定整数以下的所有质数之简单演算法，由古希腊数学家埃拉托斯特尼于公元前3世纪发明。
在古埃及人的幸存纪录中，有迹象显示他们对质数已有部分认识：例如，在莱因德数学纸草书中的古埃及分数展开时，对质数与对合数有著完全不同的类型。不过，对质数有过具体研究的最早幸存纪录来自古希腊。公元前300年左右的《几何原本》包含与质数有关的重要定理，如有无限多个质数，以及算术基本定理。欧几里得亦展示如何从梅森质数建构出完全数。埃拉托斯特尼提出的埃拉托斯特尼筛法是用来计算质数的一个简单方法，虽然今天使用电脑发现的大质数无法使用这个方法找出。
希腊之后，到17世纪之前，质数的研究少有进展。1640年，皮埃尔·德·费马叙述了费马小定理（之后才被莱布尼茨与欧拉证明）。费马亦推测，所有具
2
2
n
+
1
{\displaystyle 2^{2^{n}}+1}
形式的数均为质数（称之为费马数），并验证至
n
=
4
{\displaystyle n=4}
（即216 + 1）不过，后来由欧拉发现，下一个费马数232 + 1即为合数，且实际上其他已知的费马数都不是质数。法国修道士马兰·梅森发现有的质数具
2
p
−
1
{\displaystyle 2^{p}-1}
的形式，其中
p
{\displaystyle p}
为质数。为纪念他的贡献，此类质数后来被称为梅森质数。
欧拉在数论中的成果，许多与质数有关。他证明无穷级数
1
2
+
1
3
+
1
5
+
1
7
+
1
11
+
…
{\displaystyle {\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+{\frac {1}{11}}+\ldots }
会发散。1747年，欧拉证明每个偶完全数都确实为
2
p
−
1
(
2
p
−
1
)
{\displaystyle 2^{p-1}(2^{p}-1)}
的形式，其中第二个因数为梅森质数。
19世纪初，勒壤得与高斯独立推测，当
x
{\displaystyle x}
趋向无限大时，小于
x
{\displaystyle x}
的质数数量会趋近于
x
ln
x
{\displaystyle {\frac {x}{\ln x}}}
，其中
ln
x
{\displaystyle \ln x}
为
x
{\displaystyle x}
的自然对数。黎曼于1859年有关ζ函数的论文（英语：On the Number of Primes Less Than a Given Magnitude）中勾勒出一个程式，导出了质数定理的证明。其大纲由雅克·阿达马与夏尔-让·德拉瓦莱·普桑所完成，他们于1896年独立证明出质数定理。
证明一个大数是否为质数通常无法由试除法来达成。许多数学家已研究过大数的质数测试，通常局限于特定的数字形式。其中包括费马数的贝潘测试（英语：Pépin's test）（1877年）、普罗丝定理（约1878年）、卢卡斯-莱默质数判定法（1856年起）[13]及广义卢卡斯质数测试（英语：Lucas primality test）。较近期的演算法，如APRT-CL（英语：Adleman–Pomerance–Rumely primality test）、ECPP（英语：Elliptic curve primality）及AKS等，均可作用于任意数字上，但仍慢上许多。
长期以来，质数被认为在纯数学以外的地方只有极少数的应用[14]。到了1970年代，发明公共密钥加密这个概念之后，情况改变了，质数变成了RSA加密演算法等一阶演算法之基础。
自1951年以来，所有已知最大的质数都由电脑所发现。对更大质数的搜寻已在数学界以外的地方产生出兴趣。网际网路梅森质数大搜索及其他用来寻找大质数的分散式运算计画变得流行，在数学家仍持续与质数理论奋斗的同时。
素数的数目[编辑]
主条目：欧几里得定理
存在无限多个质数。另一种说法为，质数序列
2, 3, 5, 7, 11, 13, ...
永远不会结束。此一陈述被称为“欧几里得定理”，以古希腊数学家欧几里得为名，因为他提出了该陈述的第一个证明。已知存在其他更多的证明，包括欧拉的分析证明、哥德巴赫依据费马数的证明[15]、弗斯滕伯格使用一般拓扑学的证明[16]，以及库默尔优雅的证明[17]。
欧几里得的证明[编辑]
欧几里得的证明[18]取任一个由质数所组成的有限集合
S
{\displaystyle S}
。该证明的关键想法为考虑
S
{\displaystyle S}
内所有质数相乘后加一的一个数字：
N
=
1
+
∏
p
∈
S
p
{\displaystyle N=1+\prod _{p\in S}p}
。
如同其他自然数一般，
N
{\displaystyle N}
可被至少一个质数整除（即使N本身为质数亦同）。
任何可整除N的质数都不可能是有限集合
S
{\displaystyle S}
内的元素（质数），因为后者除N都会馀1。所以，
N
{\displaystyle N}
可被其他质数所整除。因此，任一个由质数所组成的有限集合，都可以扩展为更大个由质数所组成之集合。
这个证明通常会被错误地描述为，欧几里得一开始假定一个包含所有质数的集合，并导致矛盾；或者是，该集合恰好包含n个最小的质数，而不任意个由质数所组成之集合[19]。今日，
n
{\displaystyle n}
个最小质数相乘后加一的一个数字，被称为第
n
{\displaystyle n}
个欧几里得数。
欧拉的解析证明[编辑]
欧拉的证明使用到质数倒数的总和
S
(
p
)
=
1
2
+
1
3
+
1
5
+
1
7
+
⋯
+
1
p
{\displaystyle S(p)={\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+\cdots +{\frac {1}{p}}}
。
当
p
{\displaystyle p}
够大时，该和会大于任意实数[20]。这可证明，存在无限多个质数，否则该和将只会增长至达到最大质数
p
{\displaystyle p}
为止。
S
(
p
)
{\displaystyle S(p)}
的增加率可使用梅滕斯第二定理来量化[21]。比较总和
1
1
2
+
1
2
2
+
1
3
2
+
⋯
+
1
n
2
=
∑
i
=
1
n
1
i
2
{\displaystyle {\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{n^{2}}}=\sum _{i=1}^{n}{\frac {1}{i^{2}}}}
当
n
{\displaystyle n}
趋向无限大时，此和不会变成无限大（见巴塞尔问题）。这意味著，质数比自然数的平方更常出现。布朗定理指出，孪生质数倒数的总和
(
1
3
+
1
5
)
+
(
1
5
+
1
7
)
+
(
1
11
+
1
13
)
+
⋯
=
∑
p
prime,
p
+
2
prime
(
1
p
+
1
p
+
2
)
,
{\displaystyle \left({{\frac {1}{3}}+{\frac {1}{5}}}\right)+\left({{\frac {1}{5}}+{\frac {1}{7}}}\right)+\left({{\frac {1}{11}}+{\frac {1}{13}}}\right)+\cdots =\sum \limits _{\begin{smallmatrix}p{\text{ prime, }}\\p+2{\text{ prime}}\end{smallmatrix}}{\left({{\frac {1}{p}}+{\frac {1}{p+2}}}\right)},}
是有限的。
测试质数与整数分解[编辑]
确认一个数
n
{\displaystyle n}
是否为质数有许多种方法。最基本的程序为试除法，但因为速率很慢，没有什么实际用处。有一类现代的质数测试可适用于任意数字之上，另有一类更有效率的测试方法，则只能适用于特定的数字之上。大多数此类方法只能辨别
n
{\displaystyle n}
是否为质数。也能给出
n
{\displaystyle n}
的一个（或全部）质因数之程序称之为因数分解演算法。
试除法[编辑]
主条目：试除法
测试
n
{\displaystyle n}
是否为质数的最基本方法为试除法。此一程序将n除以每个大于1且小于等于
n
{\displaystyle n}
的平方根之整数
m
{\displaystyle m}
。若存在一个相除为整数的结果，则
n
{\displaystyle n}
不是质数；反之则是个质数。实际上，若
n
=
a
b
{\displaystyle n=ab}
是个合数（其中
a
{\displaystyle a}
与
b
≠
1
{\displaystyle b\neq 1}
），则其中一个因数
a
{\displaystyle a}
或
b
{\displaystyle b}
必定至大为
n
{\displaystyle {\sqrt {n}}}
。例如，对
n
=
37
{\displaystyle n=37}
使用试除法，将37除以
m
=
2
,
3
,
4
,
5
,
6
{\displaystyle m=2,3,4,5,6}
，没有一个数能整除37，因此37为质数。此一程序若能知道直至
n
{\displaystyle {\sqrt {n}}}
的所有质数列表，则可以只检查
m
{\displaystyle m}
为质数的状况，以提升效率。例如，为检查37是否为质数，只有3个相除是必要的（
m
=
2
,
3
,
5
{\displaystyle m=2,3,5}
），因为4与6为合数。
作为一个简单的方法，试除法在测试大整数时很快地会变得不切实际，因为可能的因数数量会随著n的增加而迅速增加。依据下文所述之质数定理，小于
n
{\displaystyle {\sqrt {n}}}
的质数之数量约为
n
ln
n
{\displaystyle {\frac {\sqrt {n}}{\ln {\sqrt {n}}}}}
，因此使用试除法测试
n
{\displaystyle n}
是否为质数时，大约会需要用到这么多的数字。对
n
=
10
20
{\displaystyle n=10^{20}}
，此一数值约为4.5亿，对许多实际应用而言都太过庞大。
筛法[编辑]
一个能给出某个数值以下的所有质数之演算法，称之为质数筛法，可用于只使用质数的试除法内。最古老的一个例子为埃拉托斯特尼筛法（见上文），至今仍最常被使用。阿特金筛法为另外一例。在电脑出现之前，筛法曾被用来给出107以下的质数列表[22]。
质数测试与质数证明[编辑]
主条目：素性测试
现代测试一般的数字
n
{\displaystyle n}
是否为质数的方法可分成两个主要类型，随机（或“蒙特卡洛”）与确定性演算法。确定性演算法可肯定辨别一个数字是否为质数。例如，试除法即是个确定性演算法，因为若正确执行，该方法总是可以辨别一个质数为质数，一个合数为合数。随机演算法一般比较快，但无法完全证明一个数是否为质数。这类测试依靠部分随机的方法来测试一个给定的数字。例如，一测试在应用于质数时总是会通过，但在应用于合数时通过的机率为
p
{\displaystyle p}
。若重复这个测试
n
{\displaystyle n}
次，且每次都通过，则该数为合数的机率为
1
(
1
−
p
)
n
{\displaystyle {\frac {1}{(1-p)^{n}}}}
，会随著测试次数呈指数下滑，因此可越来越确信（虽然总是无法完全确信）该数为质数。另一方面，若测试曾失败过，则可知该数为合数。
随机测试的一个特别简单的例子为费马质数判定法，使用到对任何整数
a
{\displaystyle a}
，
n
p
≡
n
(
mod
p
)
{\displaystyle n^{p}\equiv n(\mod p)}
，其中
p
{\displaystyle p}
为质数的这个事实（费马小定理）。若想要测试一个数字
b
{\displaystyle b}
是否为质数，则可随机选择
n
{\displaystyle n}
来计算
n
b
(
mod
b
)
{\displaystyle n^{b}(\mod b)}
的值。这个测试的缺点在于，有些合数（卡迈克尔数）即使不是质数，也会符合费马恒等式，因此这个测试无法辨别质数与卡迈克尔数，最小的三个卡迈克尔数为561，1105，1729。卡迈克尔数比质数还少上许多，所以这个测试在实际应用上还是有用的。费马质数判定法更强大的延伸方法，包括贝利-PSW、米勒-拉宾与Solovay-Strassen质数测试，都保证至少在应用于合数时，有部分时候会失败。
确定性演算法不会将合数错误判定为质数。在实务上，最快的此类方法为椭圆曲线质数证明。其运算时间是透过实务分析出来的，不像最新的AKS质数测试，有已被严格证明出来的复杂度。确定性演算法通常较随机演算法来得慢，所以一般会先使用随机演算法，再采用较费时的确定性演算法。
下面表格列出一些质数测试。运算时间以被测试的数字
n
{\displaystyle n}
来表示，并对随机演算法，以
k
{\displaystyle k}
表示其测试次数。此外，
ε
{\displaystyle \varepsilon }
是指一任意小的正数，
log
{\displaystyle \log }
是指一无特定基数的对数。大O符号表示，像是在椭圆曲线质数证明里，所需之运算时间最长为一常数（与n无关，但会与ε有关）乘于log5+ε(n)。
测试
发明于
类型
运算时间
注记
AKS质数测试
2002
确定性
O
(
log
6
+
ε
(
n
)
)
{\displaystyle O(\log ^{6+\varepsilon }(n))}
椭圆曲线质数证明
1977
确定性
O
(
log
5
+
ε
(
n
)
)
{\displaystyle O(\log ^{5+\varepsilon }(n))}
“实务分析”
贝利-PSW质数测试
1980
随机
O
(
log
3
n
)
{\displaystyle O(\log ^{3}n)}
无已知反例
米勒-拉宾质数判定法
1980
随机
O
(
k
⋅
log
2
+
ε
(
n
)
)
{\displaystyle O(k\cdot \log ^{2+\varepsilon }(n))}
错误机率
4
−
k
{\displaystyle 4^{-k}}
Solovay-Strassen质数
1977
随机
O
(
k
⋅
log
3
n
)
{\displaystyle O(k\cdot \log ^{3}n)}
错误机率
2
−
k
{\displaystyle 2^{-k}}
费马质数判定法
随机
O
(
k
⋅
log
2
+
ε
(
n
)
)
{\displaystyle O(k\cdot \log ^{2+\varepsilon }(n))}
遇到卡迈克尔数时会失败
专用目的演算法与最大已知质数[编辑]
更多信息：质数列表
建构正五边形。5是个费马质数。
除了前述可应用于任何自然数n之上的测试外，一些更有效率的质数测试适用于特定数字之上。例如，卢卡斯质数测试需要知道n − 1的质因数，而卢卡斯-莱默质数测试则需要以n + 1的质因数作为输入。例如，这些测试可应用在检查
n! ± 1 = 1 · 2 · 3 · ... · n ± 1
是否为一质数。此类形式的质数称之为阶乘质数。其他具p+1或p-1之类形式的质数还包括索菲·热尔曼质数（具2p+1形式的质数，其中p为质数）、质数阶乘质数、费马质数与梅森质数（具2p − 1形式的质数，其中p为质数）。卢卡斯-雷默质数测试对这类形式的数特别地快。这也是为何自电脑出现以来，最大已知质数总会是梅森质数的原因。
费马质数具下列形式
Fk = 22k + 1,
其中，k为任意自然数。费马质数以皮埃尔·德·费马为名，他猜想此类数字Fk均为质数。费马认为Fk均为质数的理由为此串列的前5个数字（3、5、17、257及65537）为质数。不过，F5却为合数，且直至2015年发现的其他费马数字也全都是合数。一个正n边形可用尺规作图，若且唯若
n = 2i · m
其中，m为任意个不同费马质数之乘积，及i为任一自然数，包括0。
下列表格给出各种形式的最大已知质数。有些质数使用分散式计算找到。2009年，网际网路梅森质数大搜索因为第一个发现具至少1,000万个数位的质数，而获得10万美元的奖金[23]。电子前哨基金会亦为具至少1亿个数位及10亿个数位的质数分别提供15万美元及25万美元的奖金[24]。
类型
质数
数位
日期
发现者
梅森质数
282589933 − 1
23,249,425
2018年12月21日
网际网路梅森质数大搜索
非梅森质数（普罗斯数）
19,249×213,018,586 + 1
3,918,990
2007年3月26日
十七或者破产
阶乘质数
150209! + 1
712,355
2011年10月
PrimeGrid[25]
质数阶乘质数
1098133# - 1
476,311
2012年3月
PrimeGrid[26]
孪生质数s
3756801695685×2666669 ± 1
200,700
2011年12月
PrimeGrid[27]
整数分解[编辑]
主条目：整数分解
给定一合数n，给出一个（或全部）质因数的工作称之为n的因数分解。椭圆曲线分解是一个依靠椭圆曲线上的运算来分解质因数的演算法。
质数分布[编辑]
1975年，数论学家唐·察吉尔评论质数
像生长于自然数间的杂草，似乎不服从机率之外的法则，（但又）表现出惊人的规律性，并有规范其行为之法则，且以军事化的精准度遵守著这些法则[28]。
大质数的分布，如在一给定数值以下有多少质数这个问题，可由质数定理所描述；但有效描述第n个质数的公式则仍未找到。
存在任意长的连续非质数数列，如对每个正整数
n
{\displaystyle n}
，从
(
n
+
1
)
!
+
2
{\displaystyle (n+1)!+2}
至
(
n
+
1
)
!
+
n
+
1
{\displaystyle (n+1)!+n+1}
的
n
{\displaystyle n}
个连续正整数都会是合数（因为若
k
{\displaystyle k}
为2至
n
+
1
{\displaystyle n+1}
间的一整数，
(
n
+
1
)
!
+
k
{\displaystyle (n+1)!+k}
就可被k整除）。
狄利克雷定理表示，取两个互质的整数a与b，其线性多项式
p
(
n
)
=
a
+
b
n
{\displaystyle p(n)=a+bn\,}
会有无限多个质数值。该定理亦表示，这些质数值的倒数和会发散，且具有相同b的不同多项式会有差不多相同的质数比例。
有关二次多项式的相关问题则尚无较好之理解。
质数的公式[编辑]
主条目：质数公式
对于质数，还没有一个已知的有效公式。例如，米尔斯定理与赖特所提的一个定理表示，存在实常数A>1与μ，使得
⌊
A
3
n
⌋
and
⌊
2
…
2
2
μ
⌋
{\displaystyle \left\lfloor A^{3^{n}}\right\rfloor {\text{ and }}\left\lfloor 2^{\dots ^{2^{2^{\mu }}}}\right\rfloor }
对任何自然数n而言，均为质数。其中，
⌊
−
⌋
{\displaystyle \lfloor -\rfloor }
为高斯符号，表示不大于符号内数字的最大整数。第二个公式可使用伯特兰-切比雪夫定理得证（由切比雪夫第一个证得）。该定理表示，总是存在至少一个质数p，使得 n < p < 2n − 2，其中n为大于3的任一自然数。第一个公式可由威尔逊定理导出，每个不同的n会对应到不同的质数，除了数字2会有多个n对应到外。不过，这两个公式都需要先计算出A或μ的值来[29]。
不存在一个只会产生质数值的非常数多项式，即使该多项式有许多个变数。不过，存在具9个变数的丢番图方程，其参数具备以下性质：该参数为质数，若且唯若其方程组有自然数解。这可被用来获得其所有“正值”均为质数的一个公式[30]。
一特定数以下的质数之数量[编辑]
主条目：质数定理和质数计算函数
图中的曲线分别表示π(n)（蓝）、n / ln (n)（绿）与Li(n)（红）。
质数计算函数π(n)被定义为不大于n的质数之数量。例如，π(11) = 5，因为有5个质数小于或等于11。已知有演算法可比去计算每个不大于n的质数更快的速率去计算π(n)的值。质数定理表示，π(n)的可由下列公式近似给出：
π
(
n
)
≈
n
ln
n
,
{\displaystyle \pi (n)\approx {\frac {n}{\ln n}},}
亦即，π(n)与等式右边的值在n趋近于无限大时，会趋近于1。这表示，小于n的数字为质数的可能性（大约）与n的数位呈正比。对π(n)更精确的描述可由对数积分给出：
Li
(
n
)
=
∫
2
n
d
t
ln
t
{\displaystyle \operatorname {Li} (n)=\int _{2}^{n}{\frac {dt}{\ln t}}}
。
质数定理亦蕰涵著对第n个质数pn（如p1 = 2、p2 = 3等）的大小之估算：当数字大到某一程度时，pn的值会变得约略为n log(n)[31]。特别的是，质数间隙，即两个连续质数pn与pn+1间的差会变得任意地大。后者可由数列 n! + 2, n! + 3,…, n! + n（其中n为任一自然数）看出。
等差数列[编辑]
等差数列是指由被一固定数（模）q除后会得到同一馀数的自然数所组成之集合。例如：
3, 12, 21, 30, 39, ...,
是一个等差数列，模q = 9。除了3以外，其中没有一个数会是质数，因为3 + 9n = 3(1 + 3n)，所以此一数列里的其他数字均为合数。（一般来所有大于q的质数都具有q#·n + m的形式，其中0 < m < q#，且m没有不大于q的质因数。）因此，数列
a, a + q, a + 2q, a + 3q,…
只在a与q 互质（其最大公因数为1）之时，可以有无限多个质数。若满足此一必要条件，狄利克雷定理表示，该数列含有无限多个质数。下图描述q = 9时的情形：数字每遇到9的倍数就会再再由下往上缠一次。质数以红底标记。行（数列）开始于a = 3, 6, 9者至多只包含一个质数。其他行（a = 1, 2, 4, 5, 7, 8）则均包含无限多个质数。更甚之，质数以长期来看，会均匀分布于各行之中，亦即每个质数模9会与6个数其中一数同馀的机率均为1/6。
质数（以红底标计）在模9的等差数列中。
格林-陶定理证明，存在由任意多个质数组成的等差数列[32]。一个奇质数p可表示成两个平方数之和p = x2 + y2，若且唯若p同馀于1模4（费马平方和定理）。
二次多项式的质数值[编辑]
乌岚螺旋。红点表示质数。具4n2 − 2n + 41形式的质数则以蓝点标记。
欧拉指出函数
n
2
+
n
+
41
{\displaystyle n^{2}+n+41\,}
于 0 ≤ n < 40时会给出质数[33][34]，此一事实导致了艰深的代数数论，或更具体地说为黑格纳数。当n更大时，该函数会给出合数值。哈代- 李特伍德猜想（Hardy-Littlewood conjecture）能给出一个有关具整数系数a、b与c的二次多项式
f
(
n
)
=
a
x
2
+
b
x
+
c
{\displaystyle f(n)=ax^{2}+bx+c\,}
的值为质数之机率的一个渐近预测，并能以对数积分Li(n)及系数a、b、c来表示。不过，该程式已被证实难以取得：仍未知是否存在一个二次多项式（a ≠ 0）能给出无限多个质数。乌岚螺旋将所有自然数以螺旋的方法描绘。令人惊讶的是，质数会群聚在某些对角线上，表示有些二次多项式会比其他二次多项式给出更多个质数值来。
未解决的问题[编辑]
ζ函数与黎曼猜想[编辑]
主条目：黎曼猜想
ζ函数ζ(s)的图。在s=1时，该函数会有极点，亦即会趋近于无限大。
黎曼ζ函数ζ(s)被定义为一无穷级数
ζ
(
s
)
=
∑
n
=
1
∞
1
n
s
,
{\displaystyle \zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}},}
其中，s为实数部分大于1的一个复数。由算术基本定理可证得，该级数会等于下面的无穷乘积
∏
p
prime
1
1
−
p
−
s
{\displaystyle \prod _{p{\text{ prime}}}{\frac {1}{1-p^{-s}}}}
。
ζ函数与质数密切相关。例如，存在无限多个质数这个事实也可以使用ζ函数看出：若只有有限多个质数，则ζ(1)将会是个有限值。不过，调和级数1 + 1/2 + 1/3 + 1/4 + ...会发散，所以必须有无限多个质数。另一个能看见ζ函数的丰富性，并一瞥现代代数数论的例子为下面的恒等式（巴塞尔问题，由欧拉给出）：
ζ
(
2
)
=
∏
p
1
1
−
p
−
2
=
π
2
6
{\displaystyle \zeta (2)=\prod _{p}{\frac {1}{1-p^{-2}}}={\frac {\pi ^{2}}{6}}}
。
ζ(2)的倒数6/π2，是两个随机选定的数字会互质的机率[35][36]。
未被证明的“黎曼猜想”，于1859年提出，表示除s = −2, −4, ...,外，ζ函数所有的根，其实数部分均为1/2。此一猜想与质数间的关连在于，该猜想实际上是在说，质数在正整数中出现频率和统计学的随机不同；若假设为真，质数计算函数便可有效掌握，在大数时不再需要近似求值。从物理的观点来看，这大约是在说，质数分布的不规则性仅来自于随机的杂讯。从数学的观点来看，则大约是在说，质数的渐近分布（质数定理表示小于x的质数约有x/log x个）在x周围的区间内，于区间长度远小于x的平方根时亦成立。此一猜想一般认为是正确的。
其他猜想[编辑]
更多信息：分类:素数猜想
除了黎曼猜想之外，还有许多其他的猜想存在。虽然这些猜想的陈述大多很简单，但许多猜想经过了数十年仍提不出证明，如4个兰道问题，从1912年提出至今仍然未解。其中一个为哥德巴赫猜想，该猜想认为每个大于2的偶数n都可表示成两个质数之和。至于2011年2月，这个猜想对最大达n = 2 · 1017的所有数字都会成立[37]。较弱形式的哥德巴赫猜想已被证明，如维诺格拉多夫定理，该定理表示每个足够大的奇数都可表示成三个质数之和。陈氏定理表示，每个足够大的偶数都可表示成一个质数与一个半质数（两个质数的乘积）之和。此外，任一个偶数均可写成六个质数之和[38]。数论研究这些问题的分支称之为加法数论。反哥德巴赫猜想，所有的正偶数n都可以表示成两个质数之差，但此猜想可由波利尼亚克猜想类推证明。
其他猜想处理是否有无限多个具某些限制的质数这类问题。据猜想，存在无限多个费波那契质数[39]与无限多个梅森质数，但没有无限多个费马质数[40]。还不知道是否存在无限多个维费里希质数与欧几里得质数。
第三种类型的猜想涉及到质数的分布情形。据猜想，存在无限多对孪生质数，即有无限多对相差2的质数（孪生质数猜想）。波利尼亚克猜想（英语：Polignac's conjecture）是比孪生质数猜想更强的一个猜想，该猜想表示存在无限多对相差2n的连续质数[41]。据猜想，存在无限多个具n2 + 1形式的质数[42]。上述猜想都是申策尔猜想的特例。布罗卡猜想表示，在两个大于2的连续质数之平方数之间，总是会有至少4个质数。勒让德猜想表示，对每个正整数n，n2与(n + 1)2间总会存在一个质数。克拉梅尔猜想可导出勒让德猜想。
应用[编辑]
长期以来，数论，尤其是对质数的研究，一般都会被认为是典型的纯数学，除了求知的趣味之外，没有其他应用。特别是，一些数论学家，如英国数学家戈弗雷·哈罗德·哈代即对其工作绝对不会有任何在军事上的重大性感到自豪[43]。然而，此一观点在1970年代时遭到粉碎，当质数被公开宣布可以作为产生公钥加密演算法的基础之时。质数现在也被用在杂凑表与伪乱数产生器（英语：Pseudo-random number generator）里。
旋转机被设计成在每个转片上有不同数目的销，在每个转片上的销的数量都会是质数，亦或是会与其他转片上的销的数量互质。这有助于在重复所有的组合之前，让所有转片的可能组合都能出现过一次。[来源请求]
国际标准书号的最后一码为校验码，其演算法使用到了11是个质数的这个事实[来源请求]。
在汽车变速箱齿轮的设计上，相邻的两个大小齿轮齿数最好设计成素数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强耐用度减少故障。
在害虫的生物生长周期与杀虫剂使用之间的关系上，杀虫剂的素数次数的使用也得到了证明。实验表明，素数次数地使用杀虫剂是最合理的：都是使用在害虫繁殖的高潮期，而且害虫很难产生抗药性[来源请求]。
以素数形式无规律变化的导弹和鱼雷可以使敌人不易拦截[来源请求]。
模一质数与有限体之运算[编辑]
主条目：模运算
“模运算”使用下列数字修改了一般的运算
{
0
,
1
,
2
,
…
,
n
−
1
}
,
{\displaystyle \{0,1,2,\dots ,n-1\},\,}
其中n是个固定的自然数，称之为“模”。计算加法、减法及乘法都与一般的运算一样，不过负数或大于n − 1的数字出现时，会被除以n所得的馀数取代。例如，对n=7，3+5为1，而不是8，因为8除以7馀1。这通常念为“3+5同馀于1模7”，并标记为
3
+
5
≡
1
(
mod
7
)
{\displaystyle 3+5\equiv 1{\pmod {7}}}
。
同样地，6 + 1 ≡ 0 (mod 7)、2 - 5 ≡ 4 (mod 7)，因为 -3 + 7 = 4，以及3 · 4 ≡ 5 (mod 7)，因为12除以7馀5。加法与乘法在整数里常见的标准性质在模运算里也依然有效。使用抽象代数的说法，由上述整数所组成之集合，亦标记为Z/nZ，且因此为一可交换环。不过，除法在模运算里不一定都是可行的。例如，对n=6，方程
3
⋅
x
≡
2
(
mod
6
)
,
{\displaystyle 3\cdot x\equiv 2{\pmod {6}},}
的解x会类比于2/3，无解，亦可透过计算3 · 0、...、3 · 5模6看出。不过，有关质数的不同性质如下：除法在模运算里是可行的，若且唯若n为质数。等价地说，n为质数，若且唯若所有满足2 ≤ m ≤ n − 1的整数m都会与n 互质，亦即其公因数只有1。实际上，对n=7，方程
3
⋅
x
≡
2
(
mod
7
)
,
{\displaystyle 3\cdot x\equiv 2\ \ (\operatorname {mod} \ 7),}
会有唯一的解x = 3。因此，对任何质数p，Z/pZ（亦标记为Fp）也会是个体，或更具体地说，是个有限体，因为该集合包含有限多（即p）个元素。
许多定理可以透过从此一抽象的方式检查Fp而导出。例如，费马小定理表示
a
p
−
1
≡
1
(
mod
p
)
{\displaystyle a^{p-1}\equiv 1(\operatorname {mod} \ p)}
，其中a为任一不被p整除的整数。该定理即可使用这些概念证得。这意味著
∑
a
=
1
p
−
1
a
p
−
1
≡
(
p
−
1
)
⋅
1
≡
−
1
(
mod
p
)
{\displaystyle \sum _{a=1}^{p-1}a^{p-1}\equiv (p-1)\cdot 1\equiv -1{\pmod {p}}}
。
吾乡-朱加猜想表示，上述公式亦是p为质数的必要条件。另一个费马小定理的推论如下：若p为2与5之外的其他质数，1/p总是个循环小数，其周期为p − 1或p − 1的因数。分数1/p依q（10以外的整数）为基底表示亦有类似的效果，只要p不是q的质因数的话。威尔逊定理表示，整数p > 1为质数，若且唯若阶乘 (p − 1)! + 1可被p整除。此外，整数n > 4为合数，若且唯若 (n − 1)!可被n整除。
其他数学里出现的质数[编辑]
许多数学领域里会大量使用到质数。举有限群的理论为例，西罗定理即是一例。该定理表示，若G是个有限群，且pn为质数p可整除G的阶的最大幂次，则G会有个pn阶的子群。此外，任意质数阶的群均为循环群（拉格朗日定理）。
公开金钥加密[编辑]
主条目：公开金钥加密
几个公开金钥加密演算法，如RSA与迪菲－赫尔曼金钥交换，都是以大质数为其基础（如512位元的质数常被用于RSA里，而1024位元的质数则一般被迪菲-赫尔曼金钥交换所采用）。RSA依靠计算出两个（大）质数的相乘会比找出相乘后的数的两个质因数容易出许多这个假设。迪菲－赫尔曼金钥交换依靠存在模幂次的有效演算法，但相反运算的离散对数仍被认为是个困难的问题此一事实。
自然里的质数[编辑]
周期蝉属里的蝉在其演化策略上使用到质数[44]。蝉会在地底下以幼虫的形态度过其一生中的大部分时间。周期蝉只会在7年、13年或17年后化蛹，然后从洞穴里出现、飞行、交配、产卵，并在至多数周后死亡。此一演化策略的原因据信是因为若出现的周期为质数年，掠食者就很难演化成以周期蝉为主食的动物[45]。若周期蝉出现的周期为非质数年，如12年，则每2年、3年、4年、6年或12年出现一次的掠食者就一定遇得到周期蝉。经过200年以后，假设14年与15年出现一次的周期蝉，其掠食者的平均数量，会比13年与17年出现一次的周期蝉，高出2%[46]。虽然相差不大，此一优势似乎已足够驱动天择，选择具质数年生命周期的这些昆虫。
据猜测，ζ函数的根与复数量子系统的能阶有关[47]。
推广[编辑]
质数的概念是如此的重要，以致此一概念被以不同方式推广至数学的不同领域里去。通常，“质”（prime）可在适当的意义下，用来表示具有最小性或不可分解性。例如，质体是指一个包含0与1的体F的最小子体。质体必为有理数或具有p个元素的有限体，这也是其名称的缘由[48]。若任一物件基本上均可唯一地分解成较小的部分，则这些较小的部分也会用“质”这个字来形容。例如，在纽结理论里，质纽结是指不可分解的纽结，亦即该纽结不可写成两个非平凡纽结的连通和。任一纽结均可唯一地表示为质纽约的连通和[49]。质模型与三维质流形亦为此类型的例子。
环内的素元[编辑]
主条目：素元和不可约元素
质数应用于任一可交换环R（具加法、减法与乘法的代数结构）的元素，可产生两个更为一般的概念：“素元”与“不可约元素”。R的元素称为素元，若该元素不为0或单位元素，且给定R内的元素x与y，若p可除以xy，则p可除以x或y。一元素称为不可约元素，若该元素不为单位元素，且无法写成两个不是单位元素之环元素的乘积。在整数环Z里，由素元所组成的集合等于由不可约元素所组成的集合，为
{
…
,
−
11
,
−
7
,
−
5
,
−
3
,
−
2
,
2
,
3
,
5
,
7
,
11
,
…
}
{\displaystyle \{\dots ,-11,-7,-5,-3,-2,2,3,5,7,11,\dots \}\,}
。
在任一环R里，每个素元都是不可约元素。反之不一定成立，但在唯一分解整环里会成立。
算术基本定理在唯一分解整环里仍然成立。此类整环的一个例子为高斯整数Z[i]，由具a + bi（其中a与b为任意整数）形式的复数所组成之集合。其素元称之为“高斯质数”。不是所有的质数都是高斯质数：在这个较大的环Z[i]之中，2可被分解成两个高斯质数 (1 + i)与 (1 - i)之乘积。有理质数（即在有理数里的素元），具4k+3形式者为高斯素数；具4k+1形式者则不是。
质理想[编辑]
主条目：质理想
在环论里，数的概念一般被理想所取代。“质理想”广义化了质元素的概念，为由质元素产生的主理想，是在交换代数、代数数论与代数几何里的重要工具与研究对象。整数环的质理想为理想 (0)、(2)、(3)、(5)、(7)、(11)、…算术基本定理被广义化成准素分解，可将每个在可交换诺特环里的理想表示成准素理想（为质数幂次的一适合广义化）的交集[50]。
透过环的谱这个概念，质理想成为代数几何物件的点[51]。算术几何也受益于这个概念，且许多概念会同时存在于几何与数论之内。例如，对一扩张体的质理想分解（这是代数数论里的一个基本问题），与几何里的分歧具有某些相似之处。此类分歧问题甚至在只关注整数的数论问题里也会出现。例如，二次体的整数环内的质理想可被用来证明二次互反律。二次互反律讨论下面二次方程
x
2
≡
p
(
mod
q
)
,
{\displaystyle x^{2}\equiv p\ \ ({\text{mod }}q),\,}
是否有整数解，其中x为整数，p与q为（一般）质数[52]。早期对费马最后定理证明之尝试，于恩斯特·库默尔引入正则素数后达到了高潮。正则质数是指无法在由下列式子（其中a0、…、ap−1为整数，ζ则是能使ζp = 1的复数）
a
0
+
a
1
ζ
+
⋯
+
a
p
−
1
ζ
p
−
1
,
{\displaystyle a_{0}+a_{1}\zeta +\cdots +a_{p-1}\zeta ^{p-1}\,,}
组成的环里，使得唯一分解定理失效的质数[53]。
赋值[编辑]
赋值理论研究由一个体K映射至实数R的某个函数（称之为赋值）[54]。每个此类赋值都能给出一个 K上的拓扑，且两个赋值被称为等价，若两者有相同拓扑。K的质数为一赋值的等价类。例如，一个有理数q的p进赋值被定义为整数vp(q)，使得
q
=
p
v
p
(
q
)
r
s
,
{\displaystyle q=p^{v_{p}(q)}{\frac {r}{s}},}
其中r与s不被p所整除。例如，v3(18/7) = 2。p进范数被定义为[nb 1]
|
q
|
p
:=
p
−
v
p
(
q
)
.
{\displaystyle \left|q\right|_{p}:=p^{-v_{p}(q)}.\,}
特别的是，当一个数字乘上p时，其范数会变小，与一般的绝对赋值（亦称为无限质数）形成明显的对比。当透过绝对赋值完备有理数会得出由实数所组成的体，透过p进范数完备有理数则会得出由p进数所组成的体[55]。实际上，依据奥斯特洛夫斯基定理，上述两种方法是完备有理数的所有方法。一些与有理数或更一般化之大域体有关的算术问题，可能可以被转换至完备（或局部）体上。此一局部-全域原则再次地强调了质数对于数论的重要性。
在艺术与文学里[编辑]
质数也影响了许多的艺术家与作家。法国作曲家奥立佛·梅湘使用质数创造出无节拍音乐。在《La Nativite du Seigneur》与《Quatre etudes de rythme》等作品里，梅湘同时采用由不同质数给定之长度的基调，创造出不可预测的节奏：第三个练习曲《Neumes rythmiques》中出现了质数41、43、47及53。据梅湘所述，此类作曲方式是“由自然的运动，自由且不均匀的持续运动中获得的灵感”[56]。
NASA科学家卡尔·萨根在他的科幻小说《接触未来》（Contact）里，认为质数可作为与外星人沟通的一种方式。这种想法是他与美国天文学家法兰克·德雷克于1975年闲聊时形成的[57]。
许多电影，如《异次元杀阵》（Cube）、《神鬼尖兵》（Sneakers）、《越爱越美丽》（The Mirror Has Two Faces）及《美丽境界》（A Beautiful Mind），均反映出大众对质数与密码学之神秘的迷恋[58]。保罗·裘唐诺所著的小说《质数的孤独》（The Solitude of Prime Numbers）里，质数被用来比喻寂寞与孤独，被描述成整数之间的“局外人”[来源请求]。
荒木飞吕彦所创作的日本漫画《JoJo的奇妙冒险》第六部《石之海》的反派普奇神父喜欢数质数，他认为质数是孤独的数字，并透过数质数安抚他紧张的情绪。
另见[编辑]
阿德曼-波门伦斯-鲁梅利质数测试
Bonse不等式
布朗筛法
伯恩赛德定理
契博塔耶夫密度定理
中国馀数定理
卡伦数
非法质数
质数列表
梅森质数
可乘数论
普通数域筛选法
贝潘测试
实际数
质k元组
自由黎曼气体
二次剩馀问题
RSA数
光滑数
超质数
胡道尔数
幸运素数
素数判定法则
埃拉托斯特尼筛法
孪生素数
三胞胎素数
PrimeGrid
GIMPS
质数大富豪
注记[编辑]
^ Some sources also put
|
q
|
p
:=
e
−
v
p
(
q
)
.
{\displaystyle \left|q\right|_{p}:=e^{-v_{p}(q)}.\,}
.
^ GIMPS Project Discovers Largest Known Prime Number: 274,207,281-1. 互联网梅森素数大搜索计划. （原始内容存档于2019-04-07）.
^ Dudley, Underwood, Elementary number theory 2nd, W. H. Freeman and Co., 1978, ISBN 978-0-7167-0076-0 , p. 10, section 2
^ Dudley 1978, Section 2, Theorem 2
^ Dudley 1978, Section 2, Lemma 5
^ 如见David E. Joyce对几何原本的注记，Book VII, definitions 1 and 2 （页面存档备份，存于互联网档案馆）
^ 6.0 6.1 存档副本. [2015-08-23]. （原始内容存档于2015-04-19）.
^ Weisstein, Eric W., "Goldbach Conjecture," MathWorld
^ Riesel 1994, p. 36
^ Conway & Guy 1996, pp. 129–130
^
Derbyshire, John, The Prime Number Theorem, Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics, Washington, D.C.: Joseph Henry Press: 33, 2003, ISBN 978-0-309-08549-6, OCLC 249210614 使用|accessdate=需要含有|url= (帮助)
^ ""Arguments for and against the primality of 1 （页面存档备份，存于互联网档案馆）".
^ "Why is the number one not prime?". [2015-08-23]. （原始内容存档于2008-05-09）.
^ The Largest Known Prime by Year: A Brief History （页面存档备份，存于互联网档案馆） Prime Curios!: 17014…05727 (39-digits) （页面存档备份，存于互联网档案馆）
^ 例如，Beiler写道，数论学家恩斯特·库默尔热爱他的理想数，该数与质数密切相关，“因为这些数没有被任何实际应用所玷污”。Katz则写道，爱德蒙·兰道（他最为人所知的是对质数分布的相关研究）“厌恶数学的实际应用”，且因为这个理由，规避几何等已知有所用途之学科。Beiler, Albert H., Recreations in the Theory of Numbers: The Queen of Mathematics Entertains, Dover: 2, 1966 [2015-08-23], ISBN 9780486210964, （原始内容存档于2021-04-17） . Katz, Shaul, Berlin roots—Zionist incarnation: the ethos of pure mathematics and the beginnings of the Einstein Institute of Mathematics at the Hebrew University of Jerusalem, Science in Context, 2004, 17 (1-2): 199–234, MR 2089305, doi:10.1017/S0269889704000092
^ Letter （页面存档备份，存于互联网档案馆） in Latin from Goldbach to Euler, July 1730.
^ Furstenberg 1955
^ Ribenboim 2004, p. 4
^ James Williamson (translator and commentator), The Elements of Euclid, With Dissertations, Clarendon Press, Oxford, 1782, page 63, English translation of Euclid's proof （页面存档备份，存于互联网档案馆）
^ Hardy, Michael; Woodgold, Catherine. Prime Simplicity. Mathematical Intelligencer. 2009, 31 (4): 44–52. doi:10.1007/s00283-009-9064-8.
^ Apostol, Tom M., Introduction to Analytic Number Theory, Berlin, New York: Springer-Verlag, 1976, ISBN 978-0-387-90163-3 , Section 1.6, Theorem 1.13
^ Apostol 1976, Section 4.8, Theorem 4.12
^ （Lehmer 1909）.
^ Record 12-Million-Digit Prime Number Nets $100,000 Prize. Electronic Frontier Foundation. 2009-10-14 [2010-01-04]. （原始内容存档于2021-01-20）.
^ EFF Cooperative Computing Awards. Electronic Frontier Foundation. [2010-01-04]. （原始内容存档于2010-04-02）.
^ Chris K. Caldwell. The Top Twenty: Factorial. Primes.utm.edu. [2013-02-05]. （原始内容存档于2013-04-10）.
^ Chris K. Caldwell. The Top Twenty: Primorial. Primes.utm.edu. [2013-02-05]. （原始内容存档于2021-05-06）.
^ Chris K. Caldwell. The Top Twenty: Twin Primes. Primes.utm.edu. [2013-02-05]. （原始内容存档于2013-01-27）.
^ Havil 2003, p. 171
^ Serge Tabachnikov. Kvant Selecta Algebra and Analysis. American Mathematical Society. 1999-01-01: 13– [2015-08-25]. ISBN 978-0-8218-1915-9. （原始内容存档于2021-04-17）.
^ Matiyasevich, Yuri V., Formulas for Prime Numbers, Tabachnikov, Serge (编), Kvant Selecta: Algebra and Analysis, II, American Mathematical Society: 13–24, 1999 [2015-08-23], ISBN 978-0-8218-1915-9, （原始内容存档于2021-04-17）
^ （Tom M. Apostol 1976）, Section 4.6, Theorem 4.7
^ （Ben Green & Terence Tao 2008）
^ Hua 2009，第176-177页.
^ Wolfram, Stephen. "evaluate x^2−x+41 for x from 0..40". from Wolfram Alpha: Computational Knowledge Engine, Wolfram Research. [2021-05-18]. （原始内容存档于2020-03-21） （英语）.
^ Caldwell, Chris. What is the probability that gcd(n,m)=1?. The Prime Pages. [2013-09-06]. （原始内容存档于2021-04-21）.
^ C. S. Ogilvy & J. T. Anderson Excursions in Number Theory, pp. 29–35, Dover Publications Inc., 1988 ISBN 978-0-486-25778-5
^ Tomás Oliveira e Silva. Goldbach conjecture verification. Ieeta.pt. 2011-04-09 [2011-05-21]. （原始内容存档于2013-04-21）.
^ Ramaré, O., On šnirel'man's constant, Annali della Scuola Normale Superiore di Pisa. Classe di Scienze. Serie IV, 1995, 22 (4): 645–706 [2008-08-22], （原始内容存档于2020-09-19）.
^ Caldwell, Chris, The Top Twenty: Lucas Number （页面存档备份，存于互联网档案馆） at The Prime Pages.
^ E.g., see Guy 1981, problem A3, pp. 7–8
^ Tattersall, J.J., Elementary number theory in nine chapters, Cambridge University Press, 2005 [2015-08-23], ISBN 978-0-521-85014-8, （原始内容存档于2020-03-21） , p. 112
^ Weisstein, Eric W. (编). Landau's Problems. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英语）.
^ Hardy 1940 "No one has yet discovered any warlike purpose to be served by the theory of numbers or relativity, and it seems unlikely that anyone will do so for many years."
^ Goles, E.; Schulz, O.; Markus, M. Prime number selection of cycles in a predator-prey model. Complexity. 2001, 6 (4): 33–38. doi:10.1002/cplx.1040.
^ Paulo R. A. Campos, Viviane M. de Oliveira, Ronaldo Giro, and Douglas S. Galvão., Emergence of Prime Numbers as the Result of Evolutionary Strategy, Physical Review Letters, 2004, 93 (9): 098107, Bibcode:2004PhRvL..93i8107C, arXiv:q-bio/0406017 , doi:10.1103/PhysRevLett.93.098107. 使用|accessdate=需要含有|url= (帮助)
^ Invasion of the Brood. The Economist. 2004-05-06 [2006-11-26]. （原始内容存档于2009-01-25）.
^ Ivars Peterson. The Return of Zeta. MAA Online. 1999-06-28 [2008-03-14]. （原始内容存档于2007-10-20）.
^ Lang, Serge, Algebra, Graduate Texts in Mathematics 211, Berlin, New York: Springer-Verlag, 2002, ISBN 978-0-387-95385-4, MR 1878556 , Section II.1, p. 90
^ Schubert, H. "Die eindeutige Zerlegbarkeit eines Knotens in Primknoten". S.-B Heidelberger Akad. Wiss. Math.-Nat. Kl. 1949 (1949), 57–104.
^ Eisenbud 1995, section 3.3.
^ Shafarevich, Basic Algebraic Geometry volume 2 (Schemes and Complex Manifolds), p. 5, section V.1
^ Neukirch, Algebraic Number theory, p. 50, Section I.8
^ Neukirch, Algebraic Number theory, p. 38, Section I.7
^ Endler, Valuation Theory, p. 1
^ Gouvea: p-adic numbers: an introduction, Chapter 3, p. 43
^ Hill 1995.
^ Carl Pomerance. Prime Numbers and the Search for Extraterrestrial Intelligence (PDF). [2007-12-22]. （原始内容存档 (PDF)于2021-05-06）.
^ The music of primes. [2015-08-23]. （原始内容存档于2015-10-09）.
参考资料[编辑]
Apostol, Thomas M., Introduction to Analytic Number Theory, New York: Springer, 1976, ISBN 0-387-90163-9
Conway, John Horton; Guy, Richard K., The Book of Numbers, New York: Copernicus, 1996, ISBN 978-0-387-97993-9
Crandall, Richard; Pomerance, Carl, Prime Numbers: A Computational Perspective 2nd, Berlin, New York: Springer-Verlag, 2005, ISBN 978-0-387-25282-7
Derbyshire, John, Prime obsession, Joseph Henry Press, Washington, DC, 2003, ISBN 978-0-309-08549-6, MR 1968857
Eisenbud, David, Commutative algebra, Graduate Texts in Mathematics 150, Berlin, New York: Springer-Verlag, 1995, ISBN 978-0-387-94268-1, MR 1322960
Fraleigh, John B., A First Course In Abstract Algebra 2nd, Reading: Addison-Wesley, 1976, ISBN 0-201-01984-1
Furstenberg, Harry, On the infinitude of primes, The American Mathematical Monthly (Mathematical Association of America), 1955, 62 (5): 353, JSTOR 2307043, doi:10.2307/2307043
Green, Ben; Tao, Terence, The primes contain arbitrarily long arithmetic progressions, Annals of Mathematics, 2008, 167 (2): 481–547, arXiv:math.NT/0404188 , doi:10.4007/annals.2008.167.481
Gowers, Timothy, Mathematics: A Very Short Introduction, Oxford University Press, 2002, ISBN 978-0-19-285361-5
Guy, Richard K., Unsolved Problems in Number Theory, Berlin, New York: Springer-Verlag, 1981, ISBN 978-0-387-90593-8
Havil, Julian, Gamma: Exploring Euler's Constant, Princeton University Press, 2003, ISBN 978-0-691-09983-5
Hardy, Godfrey Harold, A Course of Pure Mathematics, Cambridge University Press, 1908, ISBN 978-0-521-09227-2
Hardy, Godfrey Harold, A Mathematician's Apology, Cambridge University Press, 1940, ISBN 978-0-521-42706-7
Herstein, I. N., Topics In Algebra, Waltham: Blaisdell Publishing Company, 1964, ISBN 978-1114541016
Hill, Peter Jensen (编), The Messiaen companion, Portland, Or: Amadeus Press, 1995, ISBN 978-0-931340-95-6
Hua, L.K., Additive Theory of Prime Numbers, Translations of Mathematical Monographs 13, Providence, RI: American Mathematical Society: 176–177, 2009 [1965], ISBN 978-0821849422, MR 0194404, OCLC 824812353
Lehmer, D. H., Factor table for the first ten millions containing the smallest factor of every number not divisible by 2, 3, 5, or 7 between the limits 0 and 10017000, Washington, D.C.: Carnegie Institution of Washington, 1909
McCoy, Neal H., Introduction To Modern Algebra, Revised Edition, Boston: Allyn and Bacon, 1968, LCCN 68-15225
Narkiewicz, Wladyslaw, The development of prime number theory: from Euclid to Hardy and Littlewood, Springer Monographs in Mathematics, Berlin, New York: Springer-Verlag, 2000, ISBN 978-3-540-66289-1
Ribenboim, Paulo, The little book of bigger primes, Berlin, New York: Springer-Verlag, 2004, ISBN 978-0-387-20169-6
Riesel, Hans, Prime numbers and computer methods for factorization, Basel, Switzerland: Birkhäuser, 1994, ISBN 978-0-8176-3743-9
Sabbagh, Karl, The Riemann hypothesis, Farrar, Straus and Giroux, New York, 2003, ISBN 978-0-374-25007-2, MR 1979664
du Sautoy, Marcus, The music of the primes, HarperCollins Publishers, 2003 [2015-08-23], ISBN 978-0-06-621070-4, MR 2060134, （原始内容存档于2015-09-07）
外部链接[编辑]
查看维基词典中的词条“质数”。
维基教科书中的相关电子教程：小学数学/质数与合数
Hazewinkel, Michiel (编), Prime number, 数学百科全书, Springer, 2001, ISBN 978-1-55608-010-4
Caldwell, Chris, The Prime Pages at primes.utm.edu（页面存档备份，存于互联网档案馆）.
Prime Numbers，In Our Time (BBC Radio 4)（英语：BBC Radio 4）的《In Our Time》节目。
An Introduction to Analytic Number Theory, by Ilan Vardi and Cyril Banderier（页面存档备份，存于互联网档案馆）
Plus teacher and student package: prime numbers（页面存档备份，存于互联网档案馆） from Plus, the free online mathematics magazine produced by the Millennium Mathematics Project at the University of Cambridge.
出现质数实验 （页面存档备份，存于互联网档案馆）
出现可以被整除的机率
质数产生器与计算器[编辑]
Prime Number Checker （页面存档备份，存于互联网档案馆） identifies the smallest prime factor of a number.
Fast Online primality test with factorization（页面存档备份，存于互联网档案馆） makes use of the Elliptic Curve Method (up to thousand-digits numbers, requires Java).
Huge database of prime numbers（页面存档备份，存于互联网档案馆）
Prime Numbers up to 1 trillion （页面存档备份，存于互联网档案馆）
素数发生器和校验器 （页面存档备份，存于互联网档案馆）
查论编和因数有关的整数分类简介
质因数分解
因数
元因数
除数函数
质因数
算术基本定理
依因数分解分类
质数
合数
半素数
普洛尼克数
楔形数
无平方数因数的数
幂数
质数幂
平方数
立方数
次方数
阿喀琉斯数
光滑数
正规数
粗糙数
不寻常数
依因数和分类
完全数
殆完全数
准完全数
多重完全数
Hemiperfect数
Hyperperfect number（英语：Hyperperfect number）
超完全数
元完全数
半完全数
本原半完全数
实际数
有许多因数
过剩数
本原过剩数
高过剩数
超过剩数
可罗萨里过剩数
高合成数
Superior highly composite number（英语：Superior highly composite number）
奇异数
和真因子和数列有关
不可及数
相亲数
交际数
婚约数
其他
亏数
友谊数
孤独数
卓越数
欧尔调和数
佩服数
节俭数
等数位数
奢侈数
规范控制
BNF: cb11932592t (data)
FAST: 1041241
GND: 4047263-2
J9U: 987007538747905171
LCCN: sh85093218
LNB: 000232578
NDL: 00571462
NKC: ph139050
取自“https://zh.wikipedia.org/w/index.php?title=质数&oldid=80711832”
分类：素数整数数列隐藏分类：含有访问日期但无网址的引用的页面CS1英语来源 (en)使用ISBN魔术链接的页面含有英语的条目自2022年7月有未列明来源语句的条目有未列明来源语句的条目包含BNF标识符的维基百科条目包含FAST标识符的维基百科条目包含GND标识符的维基百科条目包含J9U标识符的维基百科条目包含LCCN标识符的维基百科条目包含LNB标识符的维基百科条目包含NDL标识符的维基百科条目包含NKC标识符的维基百科条目
本页面最后修订于2024年1月29日 (星期一) 16:57。
本站的全部文字在知识共享 署名-相同方式共享 4.0协议之条款下提供，附加条款亦可能应用。（请参阅使用条款）
Wikipedia®和维基百科标志是维基媒体基金会的注册商标；维基™是维基媒体基金会的商标。
维基媒体基金会是按美国国内税收法501(c)(3)登记的非营利慈善机构。
隐私政策
关于维基百科
免责声明
行为准则
开发者
统计
Cookie声明
手机版视图
开关有限宽度模式
请问什么是质数与合数？什么是奇数与偶数呢？麻烦详细讲一下？ - 知乎
请问什么是质数与合数？什么是奇数与偶数呢？麻烦详细讲一下？ - 知乎首页知乎知学堂发现等你来答切换模式登录/注册数学数论数学证明请问什么是质数与合数？什么是奇数与偶数呢？麻烦详细讲一下？关注者3被浏览1,093关注问题写回答邀请回答好问题添加评论分享2 个回答默认排序雪珂随笔数学家 关注质数也称素数，指的是只能被1和其自身整除的正整数；合数，是若干个（至少2个）素数的乘积，其中包括至少1个大于1的正因子。能被2 整除的自然数为偶数，可表示为2n。不能被2整除的正整数为奇数，可表示为2n+1。发布于 2022-12-06 20:33赞同添加评论分享收藏喜欢收起wyl2928喜爱数字游戏 关注先说说奇数、偶数：奇数即通常所说的“单数”，像1，3，5，7，9……偶数即通常说的“双数”，像0，2，4，6，8……所谓奇、偶也就是单、双。再说质数和合数，质数与合数是相对而言。质数：一个数除了1和本身外，不被任何其他数整除，这个数就是质数；如2，3，5，7，11，13……一个数除了1和本身外，还可以被其他数整除，那么这个数是合数。像4，6，8，9，15，21，25，77……发布于 2023-08-22 15:48赞同 1添加评论分享收藏喜欢收起
质数 - 维基百科，自由的百科全书
质数 - 维基百科，自由的百科全书
跳转到内容
主菜单
主菜单
移至侧栏
隐藏
导航
首页分类索引特色内容新闻动态最近更改随机条目资助维基百科
帮助
帮助维基社群方针与指引互助客栈知识问答字词转换IRC即时聊天联络我们关于维基百科
搜索
搜索
创建账号
登录
个人工具
创建账号 登录
未登录编辑者的页面 了解详情
贡献讨论
目录
移至侧栏
隐藏
序言
1定义和例子
2算术基本定理
开关算术基本定理子章节
2.11是否为质数
3历史
4素数的数目
开关素数的数目子章节
4.1欧几里得的证明
4.2欧拉的解析证明
5测试质数与整数分解
开关测试质数与整数分解子章节
5.1试除法
5.2筛法
5.3质数测试与质数证明
5.4专用目的演算法与最大已知质数
5.5整数分解
6质数分布
开关质数分布子章节
6.1质数的公式
6.2一特定数以下的质数之数量
6.3等差数列
6.4二次多项式的质数值
7未解决的问题
开关未解决的问题子章节
7.1ζ函数与黎曼猜想
7.2其他猜想
8应用
开关应用子章节
8.1模一质数与有限体之运算
8.2其他数学里出现的质数
8.3公开金钥加密
8.4自然里的质数
9推广
开关推广子章节
9.1环内的素元
9.2质理想
9.3赋值
10在艺术与文学里
11另见
12注记
13参考资料
14外部链接
开关外部链接子章节
14.1质数产生器与计算器
开关目录
质数
136种语言
AfrikaansAlemannischAragonésÆngliscالعربيةالدارجةمصرىঅসমীয়াAsturianuAzərbaycancaتۆرکجهБашҡортсаŽemaitėškaБеларускаяБеларуская (тарашкевіца)БългарскиবাংলাBrezhonegBosanskiCatalàکوردیČeštinaЧӑвашлаCymraegDanskDeutschZazakiΕλληνικάEmiliàn e rumagnòlEnglishEsperantoEspañolEestiEuskaraفارسیSuomiVõroNa Vosa VakavitiFøroysktFrançaisNordfriiskGaeilge贛語Kriyòl gwiyannenGalegoગુજરાતીHawaiʻiעבריתहिन्दीHrvatskiHornjoserbsceKreyòl ayisyenMagyarՀայերենԱրեւմտահայերէնInterlinguaBahasa IndonesiaÍslenskaItaliano日本語PatoisLa .lojban.JawaქართულიҚазақшаភាសាខ្មែរಕನ್ನಡ한국어KurdîKernowekКыргызчаLatinaLëtzebuergeschLimburgsLombardLietuviųLatviešuМакедонскиമലയാളംМонголमराठीBahasa MelayuMaltiမြန်မာဘာသာPlattdüütschनेपालीNederlandsNorsk nynorskNorsk bokmålOccitanଓଡ଼ିଆਪੰਜਾਬੀPolskiPiemontèisپنجابیPortuguêsRomânăРусскийСаха тылаSicilianuSrpskohrvatski / српскохрватскиTaclḥitසිංහලSimple EnglishSlovenčinaSlovenščinaSoomaaligaShqipСрпски / srpskiSvenskaKiswahiliŚlůnskiதமிழ்తెలుగుТоҷикӣไทยTagalogTürkçeئۇيغۇرچە / UyghurcheУкраїнськаاردوOʻzbekcha / ўзбекчаVènetoVepsän kel’Tiếng ViệtWest-VlamsWalonWinaray吴语ХальмгייִדישYorùbáⵜⴰⵎⴰⵣⵉⵖⵜ ⵜⴰⵏⴰⵡⴰⵢⵜ文言Bân-lâm-gú粵語
编辑链接
条目讨论
简体
不转换简体繁體大陆简体香港繁體澳門繁體大马简体新加坡简体臺灣正體
阅读编辑查看历史
工具
工具
移至侧栏
隐藏
操作
阅读编辑查看历史
常规
链入页面相关更改上传文件特殊页面固定链接页面信息引用本页获取短URL下载二维码维基数据项目
打印/导出
下载为PDF可打印版
在其他项目中
维基共享资源
维基百科，自由的百科全书
各种各样的数
基本
N
⊆
Z
⊆
Q
⊆
R
⊆
C
{\displaystyle \mathbb {N} \subseteq \mathbb {Z} \subseteq \mathbb {Q} \subseteq \mathbb {R} \subseteq \mathbb {C} }
正数
R
+
{\displaystyle \mathbb {R} ^{+}}
自然数
N
{\displaystyle \mathbb {N} }
正整数
Z
+
{\displaystyle \mathbb {Z} ^{+}}
小数
有限小数
无限小数
循环小数
有理数
Q
{\displaystyle \mathbb {Q} }
代数数
A
{\displaystyle \mathbb {A} }
实数
R
{\displaystyle \mathbb {R} }
复数
C
{\displaystyle \mathbb {C} }
高斯整数
Z
[
i
]
{\displaystyle \mathbb {Z} [i]}
负数
R
−
{\displaystyle \mathbb {R} ^{-}}
整数
Z
{\displaystyle \mathbb {Z} }
负整数
Z
−
{\displaystyle \mathbb {Z} ^{-}}
分数
单位分数
二进分数
规矩数
无理数
超越数
虚数
I
{\displaystyle \mathbb {I} }
二次无理数
艾森斯坦整数
Z
[
ω
]
{\displaystyle \mathbb {Z} [\omega ]}
延伸
二元数
四元数
H
{\displaystyle \mathbb {H} }
八元数
O
{\displaystyle \mathbb {O} }
十六元数
S
{\displaystyle \mathbb {S} }
超实数
∗
R
{\displaystyle ^{*}\mathbb {R} }
大实数
上超实数
双曲复数
双复数
复四元数
共四元数（英语：Dual quaternion）
超复数
超数
超现实数
其他
质数
P
{\displaystyle \mathbb {P} }
可计算数
基数
阿列夫数
同馀
整数数列
公称值
规矩数
可定义数
序数
超限数
p进数
数学常数
圆周率
π
=
3.14159265
{\displaystyle \pi =3.14159265}
…
自然对数的底
e
=
2.718281828
{\displaystyle e=2.718281828}
…
虚数单位
i
=
−
1
{\displaystyle i={\sqrt {-{1}}}}
无限大
∞
{\displaystyle \infty }
查论编
质数（Prime number），又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。大于1的自然数若不是质数，则称之为合数（也称为合成数）。例如，5是个质数，因为其正因数只有1与5。7是个质数，因为其正因数只有1与7。而4则是个合数，因为除了1与4外，2也是其正因数。6也是个合数，因为除了1与6外，2与3也是其正因数。算术基本定理确立了质数于数论里的核心地位：任何大于1的整数均可被表示成一串唯一质数之乘积。为了确保该定理的唯一性，1被定义为不是质数，因为在因式分解中可以有任意多个1（如3、1×3、1×1×3等都是3的有效因数分解）。
古希腊数学家欧几里得于公元前300年前后证明有无限多个质数存在（欧几里得定理）。现时人们已发现多种验证质数的方法。其中试除法比较简单，但需时较长：设被测试的自然数为
n
{\displaystyle n}
，使用此方法者需逐一测试2与
n
{\displaystyle {\sqrt {n}}}
之间的质数，确保它们无一能整除
n
{\displaystyle n}
。对于较大或一些具特别形式（如梅森数）的自然数，人们通常使用较有效率的演算法测试其是否为质数（例如282589933-1是直至2018年12月为止已知最大的梅森质数[1]，也是直至2018年12月为止已知最大的质数）。虽然人们仍未发现可以完全区别质数与合数的公式，甚至研究质数分布时相当有力的筛法也会碰到奇偶性问题（也就是多种筛法都无法区别质数跟两个质数相乘的合数的问题），但已建构了质数的分布模式（亦即质数在大数时的统计模式）。19世纪晚期得到证明的质数定理指出：一个任意自然数n为质数的机率反比于其数位（或
n
{\displaystyle n}
的对数）。
许多有关质数的问题依然未解，如哥德巴赫猜想（每个大于2的偶数可表示成两个素数之和）及孪生质数猜想（存在无穷多对相差2的质数）。这些问题促进了数论各个分支的发展，主要在于数字的解析或代数方面。质数被用于资讯科技里的几个程序中，如公钥加密利用了难以将大数分解成其质因数之类的性质。质数亦在其他数学领域里形成了各种广义化的质数概念，主要出现在代数里，如质元素及质理想。
定义和例子[编辑]
一个自然数（如1、2、3、4、5、6等）若恰有两个正因数（1及此数本身），则称之为质数[2]。大于1的自然数若不是质数，则称之为合数。
数字12不是质数，因为将12以每4个分成1组，恰可分成3组（也有其他分法）。11则无法分成数量都大于1且都相同的各组，而都会有剩馀。因此，11为质数。
在数字1至6间，数字2、3与5为质数，1、4与6则不是质数。1不是质数，其理由见下文。2是质数，因为只有1与2可整除该数。接下来，3亦为质数，因为1与3可整除3，3除以2会馀1。因此，3为质数。不过，4是合数，因为2是另一个（除1与4外）可整除4的数：
4 = 2 · 2
5又是个质数：数字2、3与4均不能整除5。接下来，6会被2或3整除，因为
6 = 2 · 3
因此，6不是质数。右图显示12不是质数：12 = 3 · 4。不存在大于2的偶数为质数，因为依据定义，任何此类数字
n
{\displaystyle n}
均至少有三个不同的因数，即1、2与
n
{\displaystyle n}
。这意指
n
{\displaystyle n}
不是质数。因此，“奇质数”系指任何大于2的质数。类似地，当使用一般的十进位制时，所有大于5的质数，其尾数均为1、3、7或9，因为尾数0、2、4、6、8为2的倍数，尾数为0或5的数字为5的倍数。
若
n
{\displaystyle n}
为一自然数，则1与
n
{\displaystyle n}
会整除
n
{\displaystyle n}
。因此，质数的条件可重新叙述为：一个数字为质数，若该数大于1，且没有
2
,
3
,
…
,
n
−
1
{\displaystyle 2,3,\ldots ,n-1}
会整除
n
{\displaystyle n}
。另一种叙述方式为：一数
n
>
1
{\displaystyle n>1}
为质数，若不能写成两个整数
a
{\displaystyle a}
与
b
{\displaystyle b}
的乘积，其中这两数均大于1：
n
=
a
⋅
b
{\displaystyle n=a\cdot b}
.
换句话说，
n
{\displaystyle n}
为质数，若
n
{\displaystyle n}
无法分成数量都大于1且都相同的各组。
由所有质数组成之集合通常标记为P或
P
{\displaystyle \mathbb {P} }
。
前168个质数（所有小于1000的质数）为2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, ...（OEIS数列A000040）。
算术基本定理[编辑]
主条目：算术基本定理
质数对于数论与一般数学的重要性来自于“算术基本定理”。该定理指出，每个大于1的整数均可写成一个以上的质数之乘积，且除了质因数的排序不同外是唯一的[3]。质数可被认为是自然数的“基本建材”，例如：
23244
= 2 · 2 · 3 · 13 · 149
= 22 · 3 · 13 · 149. （22表示2的平方或2次方。）
如同此例一般，相同的因数可能出现多次。一个数n的分解：
n
=
p
1
⋅
p
2
⋅
…
⋅
p
t
{\displaystyle n=p_{1}\cdot p_{2}\cdot \ldots \cdot p_{t}}
成（有限多个）质因数
p
1
{\displaystyle p_{1}}
、
p
2
{\displaystyle p_{2}}
、……、
p
t
{\displaystyle p_{t}}
，称之为
n
{\displaystyle n}
的“因数分解”。算术基本定理可以重新叙述为，任一质数分解除了因数的排序外，都是唯一的。因此，尽管实务上存在许多质数分解演算法来分解较大的数字，但最后都会得到相同的结果。
若
p
{\displaystyle p}
为质数，且
p
{\displaystyle p}
可整除整数的乘积
a
b
{\displaystyle ab}
，则
p
{\displaystyle p}
可整除
a
{\displaystyle a}
或可整除
b
{\displaystyle b}
。此一命题被称为欧几里得引理[4]，被用来证明质数分解的唯一性。
1是否为质数[编辑]
最早期的希腊人甚至不将1视为是一个数字[5]，因此不会认为1是质数。到了中世纪与文艺复兴时期，许多数学家将1纳入作为第一个质数[6]。到18世纪中期，克里斯蒂安·哥德巴赫在他与李昂哈德·欧拉著名的通信里将1列为第一个质数，但欧拉不同意[7]。然而，到了19世纪，仍有许多数学家认为数字1是个质数。例如，德里克·诺曼·雷默（Derrick Norman Lehmer）在他那最大达10,006,721的质数列表[8]中，将1列为第1个质数[9]。昂利·勒贝格据说是最后一个称1为质数的职业数学家[10]。到了20世纪初，数学家开始认为1不是个质数，但反而作为“单位”此一特殊类别[6]。
许多数学成果在称1为质数时，仍将有效，但欧几里何的算术基本定理（如上所述）则无法不重新叙述而仍然成立。例如，数字15可分解成3 · 5及 1 · 3 · 5；若1被允许为一个质数，则这两个表示法将会被认为是将15分解至质数的不同方法，使得此一定理的陈述必须被修正。同样地，若将1视为质数，埃拉托斯特尼筛法将无法正常运作：若将1视为质数，此一筛法将会排除掉所有1的倍数（即所有其他的数），只留下数字1。此外，质数有几个1所没有的性质，如欧拉函数的对应值，以及除数函数的总和[11][12]。
历史[编辑]
埃拉托斯特尼筛法是个找出在一特定整数以下的所有质数之简单演算法，由古希腊数学家埃拉托斯特尼于公元前3世纪发明。
在古埃及人的幸存纪录中，有迹象显示他们对质数已有部分认识：例如，在莱因德数学纸草书中的古埃及分数展开时，对质数与对合数有著完全不同的类型。不过，对质数有过具体研究的最早幸存纪录来自古希腊。公元前300年左右的《几何原本》包含与质数有关的重要定理，如有无限多个质数，以及算术基本定理。欧几里得亦展示如何从梅森质数建构出完全数。埃拉托斯特尼提出的埃拉托斯特尼筛法是用来计算质数的一个简单方法，虽然今天使用电脑发现的大质数无法使用这个方法找出。
希腊之后，到17世纪之前，质数的研究少有进展。1640年，皮埃尔·德·费马叙述了费马小定理（之后才被莱布尼茨与欧拉证明）。费马亦推测，所有具
2
2
n
+
1
{\displaystyle 2^{2^{n}}+1}
形式的数均为质数（称之为费马数），并验证至
n
=
4
{\displaystyle n=4}
（即216 + 1）不过，后来由欧拉发现，下一个费马数232 + 1即为合数，且实际上其他已知的费马数都不是质数。法国修道士马兰·梅森发现有的质数具
2
p
−
1
{\displaystyle 2^{p}-1}
的形式，其中
p
{\displaystyle p}
为质数。为纪念他的贡献，此类质数后来被称为梅森质数。
欧拉在数论中的成果，许多与质数有关。他证明无穷级数
1
2
+
1
3
+
1
5
+
1
7
+
1
11
+
…
{\displaystyle {\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+{\frac {1}{11}}+\ldots }
会发散。1747年，欧拉证明每个偶完全数都确实为
2
p
−
1
(
2
p
−
1
)
{\displaystyle 2^{p-1}(2^{p}-1)}
的形式，其中第二个因数为梅森质数。
19世纪初，勒壤得与高斯独立推测，当
x
{\displaystyle x}
趋向无限大时，小于
x
{\displaystyle x}
的质数数量会趋近于
x
ln
x
{\displaystyle {\frac {x}{\ln x}}}
，其中
ln
x
{\displaystyle \ln x}
为
x
{\displaystyle x}
的自然对数。黎曼于1859年有关ζ函数的论文（英语：On the Number of Primes Less Than a Given Magnitude）中勾勒出一个程式，导出了质数定理的证明。其大纲由雅克·阿达马与夏尔-让·德拉瓦莱·普桑所完成，他们于1896年独立证明出质数定理。
证明一个大数是否为质数通常无法由试除法来达成。许多数学家已研究过大数的质数测试，通常局限于特定的数字形式。其中包括费马数的贝潘测试（英语：Pépin's test）（1877年）、普罗丝定理（约1878年）、卢卡斯-莱默质数判定法（1856年起）[13]及广义卢卡斯质数测试（英语：Lucas primality test）。较近期的演算法，如APRT-CL（英语：Adleman–Pomerance–Rumely primality test）、ECPP（英语：Elliptic curve primality）及AKS等，均可作用于任意数字上，但仍慢上许多。
长期以来，质数被认为在纯数学以外的地方只有极少数的应用[14]。到了1970年代，发明公共密钥加密这个概念之后，情况改变了，质数变成了RSA加密演算法等一阶演算法之基础。
自1951年以来，所有已知最大的质数都由电脑所发现。对更大质数的搜寻已在数学界以外的地方产生出兴趣。网际网路梅森质数大搜索及其他用来寻找大质数的分散式运算计画变得流行，在数学家仍持续与质数理论奋斗的同时。
素数的数目[编辑]
主条目：欧几里得定理
存在无限多个质数。另一种说法为，质数序列
2, 3, 5, 7, 11, 13, ...
永远不会结束。此一陈述被称为“欧几里得定理”，以古希腊数学家欧几里得为名，因为他提出了该陈述的第一个证明。已知存在其他更多的证明，包括欧拉的分析证明、哥德巴赫依据费马数的证明[15]、弗斯滕伯格使用一般拓扑学的证明[16]，以及库默尔优雅的证明[17]。
欧几里得的证明[编辑]
欧几里得的证明[18]取任一个由质数所组成的有限集合
S
{\displaystyle S}
。该证明的关键想法为考虑
S
{\displaystyle S}
内所有质数相乘后加一的一个数字：
N
=
1
+
∏
p
∈
S
p
{\displaystyle N=1+\prod _{p\in S}p}
。
如同其他自然数一般，
N
{\displaystyle N}
可被至少一个质数整除（即使N本身为质数亦同）。
任何可整除N的质数都不可能是有限集合
S
{\displaystyle S}
内的元素（质数），因为后者除N都会馀1。所以，
N
{\displaystyle N}
可被其他质数所整除。因此，任一个由质数所组成的有限集合，都可以扩展为更大个由质数所组成之集合。
这个证明通常会被错误地描述为，欧几里得一开始假定一个包含所有质数的集合，并导致矛盾；或者是，该集合恰好包含n个最小的质数，而不任意个由质数所组成之集合[19]。今日，
n
{\displaystyle n}
个最小质数相乘后加一的一个数字，被称为第
n
{\displaystyle n}
个欧几里得数。
欧拉的解析证明[编辑]
欧拉的证明使用到质数倒数的总和
S
(
p
)
=
1
2
+
1
3
+
1
5
+
1
7
+
⋯
+
1
p
{\displaystyle S(p)={\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+\cdots +{\frac {1}{p}}}
。
当
p
{\displaystyle p}
够大时，该和会大于任意实数[20]。这可证明，存在无限多个质数，否则该和将只会增长至达到最大质数
p
{\displaystyle p}
为止。
S
(
p
)
{\displaystyle S(p)}
的增加率可使用梅滕斯第二定理来量化[21]。比较总和
1
1
2
+
1
2
2
+
1
3
2
+
⋯
+
1
n
2
=
∑
i
=
1
n
1
i
2
{\displaystyle {\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{n^{2}}}=\sum _{i=1}^{n}{\frac {1}{i^{2}}}}
当
n
{\displaystyle n}
趋向无限大时，此和不会变成无限大（见巴塞尔问题）。这意味著，质数比自然数的平方更常出现。布朗定理指出，孪生质数倒数的总和
(
1
3
+
1
5
)
+
(
1
5
+
1
7
)
+
(
1
11
+
1
13
)
+
⋯
=
∑
p
prime,
p
+
2
prime
(
1
p
+
1
p
+
2
)
,
{\displaystyle \left({{\frac {1}{3}}+{\frac {1}{5}}}\right)+\left({{\frac {1}{5}}+{\frac {1}{7}}}\right)+\left({{\frac {1}{11}}+{\frac {1}{13}}}\right)+\cdots =\sum \limits _{\begin{smallmatrix}p{\text{ prime, }}\\p+2{\text{ prime}}\end{smallmatrix}}{\left({{\frac {1}{p}}+{\frac {1}{p+2}}}\right)},}
是有限的。
测试质数与整数分解[编辑]
确认一个数
n
{\displaystyle n}
是否为质数有许多种方法。最基本的程序为试除法，但因为速率很慢，没有什么实际用处。有一类现代的质数测试可适用于任意数字之上，另有一类更有效率的测试方法，则只能适用于特定的数字之上。大多数此类方法只能辨别
n
{\displaystyle n}
是否为质数。也能给出
n
{\displaystyle n}
的一个（或全部）质因数之程序称之为因数分解演算法。
试除法[编辑]
主条目：试除法
测试
n
{\displaystyle n}
是否为质数的最基本方法为试除法。此一程序将n除以每个大于1且小于等于
n
{\displaystyle n}
的平方根之整数
m
{\displaystyle m}
。若存在一个相除为整数的结果，则
n
{\displaystyle n}
不是质数；反之则是个质数。实际上，若
n
=
a
b
{\displaystyle n=ab}
是个合数（其中
a
{\displaystyle a}
与
b
≠
1
{\displaystyle b\neq 1}
），则其中一个因数
a
{\displaystyle a}
或
b
{\displaystyle b}
必定至大为
n
{\displaystyle {\sqrt {n}}}
。例如，对
n
=
37
{\displaystyle n=37}
使用试除法，将37除以
m
=
2
,
3
,
4
,
5
,
6
{\displaystyle m=2,3,4,5,6}
，没有一个数能整除37，因此37为质数。此一程序若能知道直至
n
{\displaystyle {\sqrt {n}}}
的所有质数列表，则可以只检查
m
{\displaystyle m}
为质数的状况，以提升效率。例如，为检查37是否为质数，只有3个相除是必要的（
m
=
2
,
3
,
5
{\displaystyle m=2,3,5}
），因为4与6为合数。
作为一个简单的方法，试除法在测试大整数时很快地会变得不切实际，因为可能的因数数量会随著n的增加而迅速增加。依据下文所述之质数定理，小于
n
{\displaystyle {\sqrt {n}}}
的质数之数量约为
n
ln
n
{\displaystyle {\frac {\sqrt {n}}{\ln {\sqrt {n}}}}}
，因此使用试除法测试
n
{\displaystyle n}
是否为质数时，大约会需要用到这么多的数字。对
n
=
10
20
{\displaystyle n=10^{20}}
，此一数值约为4.5亿，对许多实际应用而言都太过庞大。
筛法[编辑]
一个能给出某个数值以下的所有质数之演算法，称之为质数筛法，可用于只使用质数的试除法内。最古老的一个例子为埃拉托斯特尼筛法（见上文），至今仍最常被使用。阿特金筛法为另外一例。在电脑出现之前，筛法曾被用来给出107以下的质数列表[22]。
质数测试与质数证明[编辑]
主条目：素性测试
现代测试一般的数字
n
{\displaystyle n}
是否为质数的方法可分成两个主要类型，随机（或“蒙特卡洛”）与确定性演算法。确定性演算法可肯定辨别一个数字是否为质数。例如，试除法即是个确定性演算法，因为若正确执行，该方法总是可以辨别一个质数为质数，一个合数为合数。随机演算法一般比较快，但无法完全证明一个数是否为质数。这类测试依靠部分随机的方法来测试一个给定的数字。例如，一测试在应用于质数时总是会通过，但在应用于合数时通过的机率为
p
{\displaystyle p}
。若重复这个测试
n
{\displaystyle n}
次，且每次都通过，则该数为合数的机率为
1
(
1
−
p
)
n
{\displaystyle {\frac {1}{(1-p)^{n}}}}
，会随著测试次数呈指数下滑，因此可越来越确信（虽然总是无法完全确信）该数为质数。另一方面，若测试曾失败过，则可知该数为合数。
随机测试的一个特别简单的例子为费马质数判定法，使用到对任何整数
a
{\displaystyle a}
，
n
p
≡
n
(
mod
p
)
{\displaystyle n^{p}\equiv n(\mod p)}
，其中
p
{\displaystyle p}
为质数的这个事实（费马小定理）。若想要测试一个数字
b
{\displaystyle b}
是否为质数，则可随机选择
n
{\displaystyle n}
来计算
n
b
(
mod
b
)
{\displaystyle n^{b}(\mod b)}
的值。这个测试的缺点在于，有些合数（卡迈克尔数）即使不是质数，也会符合费马恒等式，因此这个测试无法辨别质数与卡迈克尔数，最小的三个卡迈克尔数为561，1105，1729。卡迈克尔数比质数还少上许多，所以这个测试在实际应用上还是有用的。费马质数判定法更强大的延伸方法，包括贝利-PSW、米勒-拉宾与Solovay-Strassen质数测试，都保证至少在应用于合数时，有部分时候会失败。
确定性演算法不会将合数错误判定为质数。在实务上，最快的此类方法为椭圆曲线质数证明。其运算时间是透过实务分析出来的，不像最新的AKS质数测试，有已被严格证明出来的复杂度。确定性演算法通常较随机演算法来得慢，所以一般会先使用随机演算法，再采用较费时的确定性演算法。
下面表格列出一些质数测试。运算时间以被测试的数字
n
{\displaystyle n}
来表示，并对随机演算法，以
k
{\displaystyle k}
表示其测试次数。此外，
ε
{\displaystyle \varepsilon }
是指一任意小的正数，
log
{\displaystyle \log }
是指一无特定基数的对数。大O符号表示，像是在椭圆曲线质数证明里，所需之运算时间最长为一常数（与n无关，但会与ε有关）乘于log5+ε(n)。
测试
发明于
类型
运算时间
注记
AKS质数测试
2002
确定性
O
(
log
6
+
ε
(
n
)
)
{\displaystyle O(\log ^{6+\varepsilon }(n))}
椭圆曲线质数证明
1977
确定性
O
(
log
5
+
ε
(
n
)
)
{\displaystyle O(\log ^{5+\varepsilon }(n))}
“实务分析”
贝利-PSW质数测试
1980
随机
O
(
log
3
n
)
{\displaystyle O(\log ^{3}n)}
无已知反例
米勒-拉宾质数判定法
1980
随机
O
(
k
⋅
log
2
+
ε
(
n
)
)
{\displaystyle O(k\cdot \log ^{2+\varepsilon }(n))}
错误机率
4
−
k
{\displaystyle 4^{-k}}
Solovay-Strassen质数
1977
随机
O
(
k
⋅
log
3
n
)
{\displaystyle O(k\cdot \log ^{3}n)}
错误机率
2
−
k
{\displaystyle 2^{-k}}
费马质数判定法
随机
O
(
k
⋅
log
2
+
ε
(
n
)
)
{\displaystyle O(k\cdot \log ^{2+\varepsilon }(n))}
遇到卡迈克尔数时会失败
专用目的演算法与最大已知质数[编辑]
更多信息：质数列表
建构正五边形。5是个费马质数。
除了前述可应用于任何自然数n之上的测试外，一些更有效率的质数测试适用于特定数字之上。例如，卢卡斯质数测试需要知道n − 1的质因数，而卢卡斯-莱默质数测试则需要以n + 1的质因数作为输入。例如，这些测试可应用在检查
n! ± 1 = 1 · 2 · 3 · ... · n ± 1
是否为一质数。此类形式的质数称之为阶乘质数。其他具p+1或p-1之类形式的质数还包括索菲·热尔曼质数（具2p+1形式的质数，其中p为质数）、质数阶乘质数、费马质数与梅森质数（具2p − 1形式的质数，其中p为质数）。卢卡斯-雷默质数测试对这类形式的数特别地快。这也是为何自电脑出现以来，最大已知质数总会是梅森质数的原因。
费马质数具下列形式
Fk = 22k + 1,
其中，k为任意自然数。费马质数以皮埃尔·德·费马为名，他猜想此类数字Fk均为质数。费马认为Fk均为质数的理由为此串列的前5个数字（3、5、17、257及65537）为质数。不过，F5却为合数，且直至2015年发现的其他费马数字也全都是合数。一个正n边形可用尺规作图，若且唯若
n = 2i · m
其中，m为任意个不同费马质数之乘积，及i为任一自然数，包括0。
下列表格给出各种形式的最大已知质数。有些质数使用分散式计算找到。2009年，网际网路梅森质数大搜索因为第一个发现具至少1,000万个数位的质数，而获得10万美元的奖金[23]。电子前哨基金会亦为具至少1亿个数位及10亿个数位的质数分别提供15万美元及25万美元的奖金[24]。
类型
质数
数位
日期
发现者
梅森质数
282589933 − 1
23,249,425
2018年12月21日
网际网路梅森质数大搜索
非梅森质数（普罗斯数）
19,249×213,018,586 + 1
3,918,990
2007年3月26日
十七或者破产
阶乘质数
150209! + 1
712,355
2011年10月
PrimeGrid[25]
质数阶乘质数
1098133# - 1
476,311
2012年3月
PrimeGrid[26]
孪生质数s
3756801695685×2666669 ± 1
200,700
2011年12月
PrimeGrid[27]
整数分解[编辑]
主条目：整数分解
给定一合数n，给出一个（或全部）质因数的工作称之为n的因数分解。椭圆曲线分解是一个依靠椭圆曲线上的运算来分解质因数的演算法。
质数分布[编辑]
1975年，数论学家唐·察吉尔评论质数
像生长于自然数间的杂草，似乎不服从机率之外的法则，（但又）表现出惊人的规律性，并有规范其行为之法则，且以军事化的精准度遵守著这些法则[28]。
大质数的分布，如在一给定数值以下有多少质数这个问题，可由质数定理所描述；但有效描述第n个质数的公式则仍未找到。
存在任意长的连续非质数数列，如对每个正整数
n
{\displaystyle n}
，从
(
n
+
1
)
!
+
2
{\displaystyle (n+1)!+2}
至
(
n
+
1
)
!
+
n
+
1
{\displaystyle (n+1)!+n+1}
的
n
{\displaystyle n}
个连续正整数都会是合数（因为若
k
{\displaystyle k}
为2至
n
+
1
{\displaystyle n+1}
间的一整数，
(
n
+
1
)
!
+
k
{\displaystyle (n+1)!+k}
就可被k整除）。
狄利克雷定理表示，取两个互质的整数a与b，其线性多项式
p
(
n
)
=
a
+
b
n
{\displaystyle p(n)=a+bn\,}
会有无限多个质数值。该定理亦表示，这些质数值的倒数和会发散，且具有相同b的不同多项式会有差不多相同的质数比例。
有关二次多项式的相关问题则尚无较好之理解。
质数的公式[编辑]
主条目：质数公式
对于质数，还没有一个已知的有效公式。例如，米尔斯定理与赖特所提的一个定理表示，存在实常数A>1与μ，使得
⌊
A
3
n
⌋
and
⌊
2
…
2
2
μ
⌋
{\displaystyle \left\lfloor A^{3^{n}}\right\rfloor {\text{ and }}\left\lfloor 2^{\dots ^{2^{2^{\mu }}}}\right\rfloor }
对任何自然数n而言，均为质数。其中，
⌊
−
⌋
{\displaystyle \lfloor -\rfloor }
为高斯符号，表示不大于符号内数字的最大整数。第二个公式可使用伯特兰-切比雪夫定理得证（由切比雪夫第一个证得）。该定理表示，总是存在至少一个质数p，使得 n < p < 2n − 2，其中n为大于3的任一自然数。第一个公式可由威尔逊定理导出，每个不同的n会对应到不同的质数，除了数字2会有多个n对应到外。不过，这两个公式都需要先计算出A或μ的值来[29]。
不存在一个只会产生质数值的非常数多项式，即使该多项式有许多个变数。不过，存在具9个变数的丢番图方程，其参数具备以下性质：该参数为质数，若且唯若其方程组有自然数解。这可被用来获得其所有“正值”均为质数的一个公式[30]。
一特定数以下的质数之数量[编辑]
主条目：质数定理和质数计算函数
图中的曲线分别表示π(n)（蓝）、n / ln (n)（绿）与Li(n)（红）。
质数计算函数π(n)被定义为不大于n的质数之数量。例如，π(11) = 5，因为有5个质数小于或等于11。已知有演算法可比去计算每个不大于n的质数更快的速率去计算π(n)的值。质数定理表示，π(n)的可由下列公式近似给出：
π
(
n
)
≈
n
ln
n
,
{\displaystyle \pi (n)\approx {\frac {n}{\ln n}},}
亦即，π(n)与等式右边的值在n趋近于无限大时，会趋近于1。这表示，小于n的数字为质数的可能性（大约）与n的数位呈正比。对π(n)更精确的描述可由对数积分给出：
Li
(
n
)
=
∫
2
n
d
t
ln
t
{\displaystyle \operatorname {Li} (n)=\int _{2}^{n}{\frac {dt}{\ln t}}}
。
质数定理亦蕰涵著对第n个质数pn（如p1 = 2、p2 = 3等）的大小之估算：当数字大到某一程度时，pn的值会变得约略为n log(n)[31]。特别的是，质数间隙，即两个连续质数pn与pn+1间的差会变得任意地大。后者可由数列 n! + 2, n! + 3,…, n! + n（其中n为任一自然数）看出。
等差数列[编辑]
等差数列是指由被一固定数（模）q除后会得到同一馀数的自然数所组成之集合。例如：
3, 12, 21, 30, 39, ...,
是一个等差数列，模q = 9。除了3以外，其中没有一个数会是质数，因为3 + 9n = 3(1 + 3n)，所以此一数列里的其他数字均为合数。（一般来所有大于q的质数都具有q#·n + m的形式，其中0 < m < q#，且m没有不大于q的质因数。）因此，数列
a, a + q, a + 2q, a + 3q,…
只在a与q 互质（其最大公因数为1）之时，可以有无限多个质数。若满足此一必要条件，狄利克雷定理表示，该数列含有无限多个质数。下图描述q = 9时的情形：数字每遇到9的倍数就会再再由下往上缠一次。质数以红底标记。行（数列）开始于a = 3, 6, 9者至多只包含一个质数。其他行（a = 1, 2, 4, 5, 7, 8）则均包含无限多个质数。更甚之，质数以长期来看，会均匀分布于各行之中，亦即每个质数模9会与6个数其中一数同馀的机率均为1/6。
质数（以红底标计）在模9的等差数列中。
格林-陶定理证明，存在由任意多个质数组成的等差数列[32]。一个奇质数p可表示成两个平方数之和p = x2 + y2，若且唯若p同馀于1模4（费马平方和定理）。
二次多项式的质数值[编辑]
乌岚螺旋。红点表示质数。具4n2 − 2n + 41形式的质数则以蓝点标记。
欧拉指出函数
n
2
+
n
+
41
{\displaystyle n^{2}+n+41\,}
于 0 ≤ n < 40时会给出质数[33][34]，此一事实导致了艰深的代数数论，或更具体地说为黑格纳数。当n更大时，该函数会给出合数值。哈代- 李特伍德猜想（Hardy-Littlewood conjecture）能给出一个有关具整数系数a、b与c的二次多项式
f
(
n
)
=
a
x
2
+
b
x
+
c
{\displaystyle f(n)=ax^{2}+bx+c\,}
的值为质数之机率的一个渐近预测，并能以对数积分Li(n)及系数a、b、c来表示。不过，该程式已被证实难以取得：仍未知是否存在一个二次多项式（a ≠ 0）能给出无限多个质数。乌岚螺旋将所有自然数以螺旋的方法描绘。令人惊讶的是，质数会群聚在某些对角线上，表示有些二次多项式会比其他二次多项式给出更多个质数值来。
未解决的问题[编辑]
ζ函数与黎曼猜想[编辑]
主条目：黎曼猜想
ζ函数ζ(s)的图。在s=1时，该函数会有极点，亦即会趋近于无限大。
黎曼ζ函数ζ(s)被定义为一无穷级数
ζ
(
s
)
=
∑
n
=
1
∞
1
n
s
,
{\displaystyle \zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}},}
其中，s为实数部分大于1的一个复数。由算术基本定理可证得，该级数会等于下面的无穷乘积
∏
p
prime
1
1
−
p
−
s
{\displaystyle \prod _{p{\text{ prime}}}{\frac {1}{1-p^{-s}}}}
。
ζ函数与质数密切相关。例如，存在无限多个质数这个事实也可以使用ζ函数看出：若只有有限多个质数，则ζ(1)将会是个有限值。不过，调和级数1 + 1/2 + 1/3 + 1/4 + ...会发散，所以必须有无限多个质数。另一个能看见ζ函数的丰富性，并一瞥现代代数数论的例子为下面的恒等式（巴塞尔问题，由欧拉给出）：
ζ
(
2
)
=
∏
p
1
1
−
p
−
2
=
π
2
6
{\displaystyle \zeta (2)=\prod _{p}{\frac {1}{1-p^{-2}}}={\frac {\pi ^{2}}{6}}}
。
ζ(2)的倒数6/π2，是两个随机选定的数字会互质的机率[35][36]。
未被证明的“黎曼猜想”，于1859年提出，表示除s = −2, −4, ...,外，ζ函数所有的根，其实数部分均为1/2。此一猜想与质数间的关连在于，该猜想实际上是在说，质数在正整数中出现频率和统计学的随机不同；若假设为真，质数计算函数便可有效掌握，在大数时不再需要近似求值。从物理的观点来看，这大约是在说，质数分布的不规则性仅来自于随机的杂讯。从数学的观点来看，则大约是在说，质数的渐近分布（质数定理表示小于x的质数约有x/log x个）在x周围的区间内，于区间长度远小于x的平方根时亦成立。此一猜想一般认为是正确的。
其他猜想[编辑]
更多信息：分类:素数猜想
除了黎曼猜想之外，还有许多其他的猜想存在。虽然这些猜想的陈述大多很简单，但许多猜想经过了数十年仍提不出证明，如4个兰道问题，从1912年提出至今仍然未解。其中一个为哥德巴赫猜想，该猜想认为每个大于2的偶数n都可表示成两个质数之和。至于2011年2月，这个猜想对最大达n = 2 · 1017的所有数字都会成立[37]。较弱形式的哥德巴赫猜想已被证明，如维诺格拉多夫定理，该定理表示每个足够大的奇数都可表示成三个质数之和。陈氏定理表示，每个足够大的偶数都可表示成一个质数与一个半质数（两个质数的乘积）之和。此外，任一个偶数均可写成六个质数之和[38]。数论研究这些问题的分支称之为加法数论。反哥德巴赫猜想，所有的正偶数n都可以表示成两个质数之差，但此猜想可由波利尼亚克猜想类推证明。
其他猜想处理是否有无限多个具某些限制的质数这类问题。据猜想，存在无限多个费波那契质数[39]与无限多个梅森质数，但没有无限多个费马质数[40]。还不知道是否存在无限多个维费里希质数与欧几里得质数。
第三种类型的猜想涉及到质数的分布情形。据猜想，存在无限多对孪生质数，即有无限多对相差2的质数（孪生质数猜想）。波利尼亚克猜想（英语：Polignac's conjecture）是比孪生质数猜想更强的一个猜想，该猜想表示存在无限多对相差2n的连续质数[41]。据猜想，存在无限多个具n2 + 1形式的质数[42]。上述猜想都是申策尔猜想的特例。布罗卡猜想表示，在两个大于2的连续质数之平方数之间，总是会有至少4个质数。勒让德猜想表示，对每个正整数n，n2与(n + 1)2间总会存在一个质数。克拉梅尔猜想可导出勒让德猜想。
应用[编辑]
长期以来，数论，尤其是对质数的研究，一般都会被认为是典型的纯数学，除了求知的趣味之外，没有其他应用。特别是，一些数论学家，如英国数学家戈弗雷·哈罗德·哈代即对其工作绝对不会有任何在军事上的重大性感到自豪[43]。然而，此一观点在1970年代时遭到粉碎，当质数被公开宣布可以作为产生公钥加密演算法的基础之时。质数现在也被用在杂凑表与伪乱数产生器（英语：Pseudo-random number generator）里。
旋转机被设计成在每个转片上有不同数目的销，在每个转片上的销的数量都会是质数，亦或是会与其他转片上的销的数量互质。这有助于在重复所有的组合之前，让所有转片的可能组合都能出现过一次。[来源请求]
国际标准书号的最后一码为校验码，其演算法使用到了11是个质数的这个事实[来源请求]。
在汽车变速箱齿轮的设计上，相邻的两个大小齿轮齿数最好设计成素数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强耐用度减少故障。
在害虫的生物生长周期与杀虫剂使用之间的关系上，杀虫剂的素数次数的使用也得到了证明。实验表明，素数次数地使用杀虫剂是最合理的：都是使用在害虫繁殖的高潮期，而且害虫很难产生抗药性[来源请求]。
以素数形式无规律变化的导弹和鱼雷可以使敌人不易拦截[来源请求]。
模一质数与有限体之运算[编辑]
主条目：模运算
“模运算”使用下列数字修改了一般的运算
{
0
,
1
,
2
,
…
,
n
−
1
}
,
{\displaystyle \{0,1,2,\dots ,n-1\},\,}
其中n是个固定的自然数，称之为“模”。计算加法、减法及乘法都与一般的运算一样，不过负数或大于n − 1的数字出现时，会被除以n所得的馀数取代。例如，对n=7，3+5为1，而不是8，因为8除以7馀1。这通常念为“3+5同馀于1模7”，并标记为
3
+
5
≡
1
(
mod
7
)
{\displaystyle 3+5\equiv 1{\pmod {7}}}
。
同样地，6 + 1 ≡ 0 (mod 7)、2 - 5 ≡ 4 (mod 7)，因为 -3 + 7 = 4，以及3 · 4 ≡ 5 (mod 7)，因为12除以7馀5。加法与乘法在整数里常见的标准性质在模运算里也依然有效。使用抽象代数的说法，由上述整数所组成之集合，亦标记为Z/nZ，且因此为一可交换环。不过，除法在模运算里不一定都是可行的。例如，对n=6，方程
3
⋅
x
≡
2
(
mod
6
)
,
{\displaystyle 3\cdot x\equiv 2{\pmod {6}},}
的解x会类比于2/3，无解，亦可透过计算3 · 0、...、3 · 5模6看出。不过，有关质数的不同性质如下：除法在模运算里是可行的，若且唯若n为质数。等价地说，n为质数，若且唯若所有满足2 ≤ m ≤ n − 1的整数m都会与n 互质，亦即其公因数只有1。实际上，对n=7，方程
3
⋅
x
≡
2
(
mod
7
)
,
{\displaystyle 3\cdot x\equiv 2\ \ (\operatorname {mod} \ 7),}
会有唯一的解x = 3。因此，对任何质数p，Z/pZ（亦标记为Fp）也会是个体，或更具体地说，是个有限体，因为该集合包含有限多（即p）个元素。
许多定理可以透过从此一抽象的方式检查Fp而导出。例如，费马小定理表示
a
p
−
1
≡
1
(
mod
p
)
{\displaystyle a^{p-1}\equiv 1(\operatorname {mod} \ p)}
，其中a为任一不被p整除的整数。该定理即可使用这些概念证得。这意味著
∑
a
=
1
p
−
1
a
p
−
1
≡
(
p
−
1
)
⋅
1
≡
−
1
(
mod
p
)
{\displaystyle \sum _{a=1}^{p-1}a^{p-1}\equiv (p-1)\cdot 1\equiv -1{\pmod {p}}}
。
吾乡-朱加猜想表示，上述公式亦是p为质数的必要条件。另一个费马小定理的推论如下：若p为2与5之外的其他质数，1/p总是个循环小数，其周期为p − 1或p − 1的因数。分数1/p依q（10以外的整数）为基底表示亦有类似的效果，只要p不是q的质因数的话。威尔逊定理表示，整数p > 1为质数，若且唯若阶乘 (p − 1)! + 1可被p整除。此外，整数n > 4为合数，若且唯若 (n − 1)!可被n整除。
其他数学里出现的质数[编辑]
许多数学领域里会大量使用到质数。举有限群的理论为例，西罗定理即是一例。该定理表示，若G是个有限群，且pn为质数p可整除G的阶的最大幂次，则G会有个pn阶的子群。此外，任意质数阶的群均为循环群（拉格朗日定理）。
公开金钥加密[编辑]
主条目：公开金钥加密
几个公开金钥加密演算法，如RSA与迪菲－赫尔曼金钥交换，都是以大质数为其基础（如512位元的质数常被用于RSA里，而1024位元的质数则一般被迪菲-赫尔曼金钥交换所采用）。RSA依靠计算出两个（大）质数的相乘会比找出相乘后的数的两个质因数容易出许多这个假设。迪菲－赫尔曼金钥交换依靠存在模幂次的有效演算法，但相反运算的离散对数仍被认为是个困难的问题此一事实。
自然里的质数[编辑]
周期蝉属里的蝉在其演化策略上使用到质数[44]。蝉会在地底下以幼虫的形态度过其一生中的大部分时间。周期蝉只会在7年、13年或17年后化蛹，然后从洞穴里出现、飞行、交配、产卵，并在至多数周后死亡。此一演化策略的原因据信是因为若出现的周期为质数年，掠食者就很难演化成以周期蝉为主食的动物[45]。若周期蝉出现的周期为非质数年，如12年，则每2年、3年、4年、6年或12年出现一次的掠食者就一定遇得到周期蝉。经过200年以后，假设14年与15年出现一次的周期蝉，其掠食者的平均数量，会比13年与17年出现一次的周期蝉，高出2%[46]。虽然相差不大，此一优势似乎已足够驱动天择，选择具质数年生命周期的这些昆虫。
据猜测，ζ函数的根与复数量子系统的能阶有关[47]。
推广[编辑]
质数的概念是如此的重要，以致此一概念被以不同方式推广至数学的不同领域里去。通常，“质”（prime）可在适当的意义下，用来表示具有最小性或不可分解性。例如，质体是指一个包含0与1的体F的最小子体。质体必为有理数或具有p个元素的有限体，这也是其名称的缘由[48]。若任一物件基本上均可唯一地分解成较小的部分，则这些较小的部分也会用“质”这个字来形容。例如，在纽结理论里，质纽结是指不可分解的纽结，亦即该纽结不可写成两个非平凡纽结的连通和。任一纽结均可唯一地表示为质纽约的连通和[49]。质模型与三维质流形亦为此类型的例子。
环内的素元[编辑]
主条目：素元和不可约元素
质数应用于任一可交换环R（具加法、减法与乘法的代数结构）的元素，可产生两个更为一般的概念：“素元”与“不可约元素”。R的元素称为素元，若该元素不为0或单位元素，且给定R内的元素x与y，若p可除以xy，则p可除以x或y。一元素称为不可约元素，若该元素不为单位元素，且无法写成两个不是单位元素之环元素的乘积。在整数环Z里，由素元所组成的集合等于由不可约元素所组成的集合，为
{
…
,
−
11
,
−
7
,
−
5
,
−
3
,
−
2
,
2
,
3
,
5
,
7
,
11
,
…
}
{\displaystyle \{\dots ,-11,-7,-5,-3,-2,2,3,5,7,11,\dots \}\,}
。
在任一环R里，每个素元都是不可约元素。反之不一定成立，但在唯一分解整环里会成立。
算术基本定理在唯一分解整环里仍然成立。此类整环的一个例子为高斯整数Z[i]，由具a + bi（其中a与b为任意整数）形式的复数所组成之集合。其素元称之为“高斯质数”。不是所有的质数都是高斯质数：在这个较大的环Z[i]之中，2可被分解成两个高斯质数 (1 + i)与 (1 - i)之乘积。有理质数（即在有理数里的素元），具4k+3形式者为高斯素数；具4k+1形式者则不是。
质理想[编辑]
主条目：质理想
在环论里，数的概念一般被理想所取代。“质理想”广义化了质元素的概念，为由质元素产生的主理想，是在交换代数、代数数论与代数几何里的重要工具与研究对象。整数环的质理想为理想 (0)、(2)、(3)、(5)、(7)、(11)、…算术基本定理被广义化成准素分解，可将每个在可交换诺特环里的理想表示成准素理想（为质数幂次的一适合广义化）的交集[50]。
透过环的谱这个概念，质理想成为代数几何物件的点[51]。算术几何也受益于这个概念，且许多概念会同时存在于几何与数论之内。例如，对一扩张体的质理想分解（这是代数数论里的一个基本问题），与几何里的分歧具有某些相似之处。此类分歧问题甚至在只关注整数的数论问题里也会出现。例如，二次体的整数环内的质理想可被用来证明二次互反律。二次互反律讨论下面二次方程
x
2
≡
p
(
mod
q
)
,
{\displaystyle x^{2}\equiv p\ \ ({\text{mod }}q),\,}
是否有整数解，其中x为整数，p与q为（一般）质数[52]。早期对费马最后定理证明之尝试，于恩斯特·库默尔引入正则素数后达到了高潮。正则质数是指无法在由下列式子（其中a0、…、ap−1为整数，ζ则是能使ζp = 1的复数）
a
0
+
a
1
ζ
+
⋯
+
a
p
−
1
ζ
p
−
1
,
{\displaystyle a_{0}+a_{1}\zeta +\cdots +a_{p-1}\zeta ^{p-1}\,,}
组成的环里，使得唯一分解定理失效的质数[53]。
赋值[编辑]
赋值理论研究由一个体K映射至实数R的某个函数（称之为赋值）[54]。每个此类赋值都能给出一个 K上的拓扑，且两个赋值被称为等价，若两者有相同拓扑。K的质数为一赋值的等价类。例如，一个有理数q的p进赋值被定义为整数vp(q)，使得
q
=
p
v
p
(
q
)
r
s
,
{\displaystyle q=p^{v_{p}(q)}{\frac {r}{s}},}
其中r与s不被p所整除。例如，v3(18/7) = 2。p进范数被定义为[nb 1]
|
q
|
p
:=
p
−
v
p
(
q
)
.
{\displaystyle \left|q\right|_{p}:=p^{-v_{p}(q)}.\,}
特别的是，当一个数字乘上p时，其范数会变小，与一般的绝对赋值（亦称为无限质数）形成明显的对比。当透过绝对赋值完备有理数会得出由实数所组成的体，透过p进范数完备有理数则会得出由p进数所组成的体[55]。实际上，依据奥斯特洛夫斯基定理，上述两种方法是完备有理数的所有方法。一些与有理数或更一般化之大域体有关的算术问题，可能可以被转换至完备（或局部）体上。此一局部-全域原则再次地强调了质数对于数论的重要性。
在艺术与文学里[编辑]
质数也影响了许多的艺术家与作家。法国作曲家奥立佛·梅湘使用质数创造出无节拍音乐。在《La Nativite du Seigneur》与《Quatre etudes de rythme》等作品里，梅湘同时采用由不同质数给定之长度的基调，创造出不可预测的节奏：第三个练习曲《Neumes rythmiques》中出现了质数41、43、47及53。据梅湘所述，此类作曲方式是“由自然的运动，自由且不均匀的持续运动中获得的灵感”[56]。
NASA科学家卡尔·萨根在他的科幻小说《接触未来》（Contact）里，认为质数可作为与外星人沟通的一种方式。这种想法是他与美国天文学家法兰克·德雷克于1975年闲聊时形成的[57]。
许多电影，如《异次元杀阵》（Cube）、《神鬼尖兵》（Sneakers）、《越爱越美丽》（The Mirror Has Two Faces）及《美丽境界》（A Beautiful Mind），均反映出大众对质数与密码学之神秘的迷恋[58]。保罗·裘唐诺所著的小说《质数的孤独》（The Solitude of Prime Numbers）里，质数被用来比喻寂寞与孤独，被描述成整数之间的“局外人”[来源请求]。
荒木飞吕彦所创作的日本漫画《JoJo的奇妙冒险》第六部《石之海》的反派普奇神父喜欢数质数，他认为质数是孤独的数字，并透过数质数安抚他紧张的情绪。
另见[编辑]
阿德曼-波门伦斯-鲁梅利质数测试
Bonse不等式
布朗筛法
伯恩赛德定理
契博塔耶夫密度定理
中国馀数定理
卡伦数
非法质数
质数列表
梅森质数
可乘数论
普通数域筛选法
贝潘测试
实际数
质k元组
自由黎曼气体
二次剩馀问题
RSA数
光滑数
超质数
胡道尔数
幸运素数
素数判定法则
埃拉托斯特尼筛法
孪生素数
三胞胎素数
PrimeGrid
GIMPS
质数大富豪
注记[编辑]
^ Some sources also put
|
q
|
p
:=
e
−
v
p
(
q
)
.
{\displaystyle \left|q\right|_{p}:=e^{-v_{p}(q)}.\,}
.
^ GIMPS Project Discovers Largest Known Prime Number: 274,207,281-1. 互联网梅森素数大搜索计划. （原始内容存档于2019-04-07）.
^ Dudley, Underwood, Elementary number theory 2nd, W. H. Freeman and Co., 1978, ISBN 978-0-7167-0076-0 , p. 10, section 2
^ Dudley 1978, Section 2, Theorem 2
^ Dudley 1978, Section 2, Lemma 5
^ 如见David E. Joyce对几何原本的注记，Book VII, definitions 1 and 2 （页面存档备份，存于互联网档案馆）
^ 6.0 6.1 存档副本. [2015-08-23]. （原始内容存档于2015-04-19）.
^ Weisstein, Eric W., "Goldbach Conjecture," MathWorld
^ Riesel 1994, p. 36
^ Conway & Guy 1996, pp. 129–130
^
Derbyshire, John, The Prime Number Theorem, Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics, Washington, D.C.: Joseph Henry Press: 33, 2003, ISBN 978-0-309-08549-6, OCLC 249210614 使用|accessdate=需要含有|url= (帮助)
^ ""Arguments for and against the primality of 1 （页面存档备份，存于互联网档案馆）".
^ "Why is the number one not prime?". [2015-08-23]. （原始内容存档于2008-05-09）.
^ The Largest Known Prime by Year: A Brief History （页面存档备份，存于互联网档案馆） Prime Curios!: 17014…05727 (39-digits) （页面存档备份，存于互联网档案馆）
^ 例如，Beiler写道，数论学家恩斯特·库默尔热爱他的理想数，该数与质数密切相关，“因为这些数没有被任何实际应用所玷污”。Katz则写道，爱德蒙·兰道（他最为人所知的是对质数分布的相关研究）“厌恶数学的实际应用”，且因为这个理由，规避几何等已知有所用途之学科。Beiler, Albert H., Recreations in the Theory of Numbers: The Queen of Mathematics Entertains, Dover: 2, 1966 [2015-08-23], ISBN 9780486210964, （原始内容存档于2021-04-17） . Katz, Shaul, Berlin roots—Zionist incarnation: the ethos of pure mathematics and the beginnings of the Einstein Institute of Mathematics at the Hebrew University of Jerusalem, Science in Context, 2004, 17 (1-2): 199–234, MR 2089305, doi:10.1017/S0269889704000092
^ Letter （页面存档备份，存于互联网档案馆） in Latin from Goldbach to Euler, July 1730.
^ Furstenberg 1955
^ Ribenboim 2004, p. 4
^ James Williamson (translator and commentator), The Elements of Euclid, With Dissertations, Clarendon Press, Oxford, 1782, page 63, English translation of Euclid's proof （页面存档备份，存于互联网档案馆）
^ Hardy, Michael; Woodgold, Catherine. Prime Simplicity. Mathematical Intelligencer. 2009, 31 (4): 44–52. doi:10.1007/s00283-009-9064-8.
^ Apostol, Tom M., Introduction to Analytic Number Theory, Berlin, New York: Springer-Verlag, 1976, ISBN 978-0-387-90163-3 , Section 1.6, Theorem 1.13
^ Apostol 1976, Section 4.8, Theorem 4.12
^ （Lehmer 1909）.
^ Record 12-Million-Digit Prime Number Nets $100,000 Prize. Electronic Frontier Foundation. 2009-10-14 [2010-01-04]. （原始内容存档于2021-01-20）.
^ EFF Cooperative Computing Awards. Electronic Frontier Foundation. [2010-01-04]. （原始内容存档于2010-04-02）.
^ Chris K. Caldwell. The Top Twenty: Factorial. Primes.utm.edu. [2013-02-05]. （原始内容存档于2013-04-10）.
^ Chris K. Caldwell. The Top Twenty: Primorial. Primes.utm.edu. [2013-02-05]. （原始内容存档于2021-05-06）.
^ Chris K. Caldwell. The Top Twenty: Twin Primes. Primes.utm.edu. [2013-02-05]. （原始内容存档于2013-01-27）.
^ Havil 2003, p. 171
^ Serge Tabachnikov. Kvant Selecta Algebra and Analysis. American Mathematical Society. 1999-01-01: 13– [2015-08-25]. ISBN 978-0-8218-1915-9. （原始内容存档于2021-04-17）.
^ Matiyasevich, Yuri V., Formulas for Prime Numbers, Tabachnikov, Serge (编), Kvant Selecta: Algebra and Analysis, II, American Mathematical Society: 13–24, 1999 [2015-08-23], ISBN 978-0-8218-1915-9, （原始内容存档于2021-04-17）
^ （Tom M. Apostol 1976）, Section 4.6, Theorem 4.7
^ （Ben Green & Terence Tao 2008）
^ Hua 2009，第176-177页.
^ Wolfram, Stephen. "evaluate x^2−x+41 for x from 0..40". from Wolfram Alpha: Computational Knowledge Engine, Wolfram Research. [2021-05-18]. （原始内容存档于2020-03-21） （英语）.
^ Caldwell, Chris. What is the probability that gcd(n,m)=1?. The Prime Pages. [2013-09-06]. （原始内容存档于2021-04-21）.
^ C. S. Ogilvy & J. T. Anderson Excursions in Number Theory, pp. 29–35, Dover Publications Inc., 1988 ISBN 978-0-486-25778-5
^ Tomás Oliveira e Silva. Goldbach conjecture verification. Ieeta.pt. 2011-04-09 [2011-05-21]. （原始内容存档于2013-04-21）.
^ Ramaré, O., On šnirel'man's constant, Annali della Scuola Normale Superiore di Pisa. Classe di Scienze. Serie IV, 1995, 22 (4): 645–706 [2008-08-22], （原始内容存档于2020-09-19）.
^ Caldwell, Chris, The Top Twenty: Lucas Number （页面存档备份，存于互联网档案馆） at The Prime Pages.
^ E.g., see Guy 1981, problem A3, pp. 7–8
^ Tattersall, J.J., Elementary number theory in nine chapters, Cambridge University Press, 2005 [2015-08-23], ISBN 978-0-521-85014-8, （原始内容存档于2020-03-21） , p. 112
^ Weisstein, Eric W. (编). Landau's Problems. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英语）.
^ Hardy 1940 "No one has yet discovered any warlike purpose to be served by the theory of numbers or relativity, and it seems unlikely that anyone will do so for many years."
^ Goles, E.; Schulz, O.; Markus, M. Prime number selection of cycles in a predator-prey model. Complexity. 2001, 6 (4): 33–38. doi:10.1002/cplx.1040.
^ Paulo R. A. Campos, Viviane M. de Oliveira, Ronaldo Giro, and Douglas S. Galvão., Emergence of Prime Numbers as the Result of Evolutionary Strategy, Physical Review Letters, 2004, 93 (9): 098107, Bibcode:2004PhRvL..93i8107C, arXiv:q-bio/0406017 , doi:10.1103/PhysRevLett.93.098107. 使用|accessdate=需要含有|url= (帮助)
^ Invasion of the Brood. The Economist. 2004-05-06 [2006-11-26]. （原始内容存档于2009-01-25）.
^ Ivars Peterson. The Return of Zeta. MAA Online. 1999-06-28 [2008-03-14]. （原始内容存档于2007-10-20）.
^ Lang, Serge, Algebra, Graduate Texts in Mathematics 211, Berlin, New York: Springer-Verlag, 2002, ISBN 978-0-387-95385-4, MR 1878556 , Section II.1, p. 90
^ Schubert, H. "Die eindeutige Zerlegbarkeit eines Knotens in Primknoten". S.-B Heidelberger Akad. Wiss. Math.-Nat. Kl. 1949 (1949), 57–104.
^ Eisenbud 1995, section 3.3.
^ Shafarevich, Basic Algebraic Geometry volume 2 (Schemes and Complex Manifolds), p. 5, section V.1
^ Neukirch, Algebraic Number theory, p. 50, Section I.8
^ Neukirch, Algebraic Number theory, p. 38, Section I.7
^ Endler, Valuation Theory, p. 1
^ Gouvea: p-adic numbers: an introduction, Chapter 3, p. 43
^ Hill 1995.
^ Carl Pomerance. Prime Numbers and the Search for Extraterrestrial Intelligence (PDF). [2007-12-22]. （原始内容存档 (PDF)于2021-05-06）.
^ The music of primes. [2015-08-23]. （原始内容存档于2015-10-09）.
参考资料[编辑]
Apostol, Thomas M., Introduction to Analytic Number Theory, New York: Springer, 1976, ISBN 0-387-90163-9
Conway, John Horton; Guy, Richard K., The Book of Numbers, New York: Copernicus, 1996, ISBN 978-0-387-97993-9
Crandall, Richard; Pomerance, Carl, Prime Numbers: A Computational Perspective 2nd, Berlin, New York: Springer-Verlag, 2005, ISBN 978-0-387-25282-7
Derbyshire, John, Prime obsession, Joseph Henry Press, Washington, DC, 2003, ISBN 978-0-309-08549-6, MR 1968857
Eisenbud, David, Commutative algebra, Graduate Texts in Mathematics 150, Berlin, New York: Springer-Verlag, 1995, ISBN 978-0-387-94268-1, MR 1322960
Fraleigh, John B., A First Course In Abstract Algebra 2nd, Reading: Addison-Wesley, 1976, ISBN 0-201-01984-1
Furstenberg, Harry, On the infinitude of primes, The American Mathematical Monthly (Mathematical Association of America), 1955, 62 (5): 353, JSTOR 2307043, doi:10.2307/2307043
Green, Ben; Tao, Terence, The primes contain arbitrarily long arithmetic progressions, Annals of Mathematics, 2008, 167 (2): 481–547, arXiv:math.NT/0404188 , doi:10.4007/annals.2008.167.481
Gowers, Timothy, Mathematics: A Very Short Introduction, Oxford University Press, 2002, ISBN 978-0-19-285361-5
Guy, Richard K., Unsolved Problems in Number Theory, Berlin, New York: Springer-Verlag, 1981, ISBN 978-0-387-90593-8
Havil, Julian, Gamma: Exploring Euler's Constant, Princeton University Press, 2003, ISBN 978-0-691-09983-5
Hardy, Godfrey Harold, A Course of Pure Mathematics, Cambridge University Press, 1908, ISBN 978-0-521-09227-2
Hardy, Godfrey Harold, A Mathematician's Apology, Cambridge University Press, 1940, ISBN 978-0-521-42706-7
Herstein, I. N., Topics In Algebra, Waltham: Blaisdell Publishing Company, 1964, ISBN 978-1114541016
Hill, Peter Jensen (编), The Messiaen companion, Portland, Or: Amadeus Press, 1995, ISBN 978-0-931340-95-6
Hua, L.K., Additive Theory of Prime Numbers, Translations of Mathematical Monographs 13, Providence, RI: American Mathematical Society: 176–177, 2009 [1965], ISBN 978-0821849422, MR 0194404, OCLC 824812353
Lehmer, D. H., Factor table for the first ten millions containing the smallest factor of every number not divisible by 2, 3, 5, or 7 between the limits 0 and 10017000, Washington, D.C.: Carnegie Institution of Washington, 1909
McCoy, Neal H., Introduction To Modern Algebra, Revised Edition, Boston: Allyn and Bacon, 1968, LCCN 68-15225
Narkiewicz, Wladyslaw, The development of prime number theory: from Euclid to Hardy and Littlewood, Springer Monographs in Mathematics, Berlin, New York: Springer-Verlag, 2000, ISBN 978-3-540-66289-1
Ribenboim, Paulo, The little book of bigger primes, Berlin, New York: Springer-Verlag, 2004, ISBN 978-0-387-20169-6
Riesel, Hans, Prime numbers and computer methods for factorization, Basel, Switzerland: Birkhäuser, 1994, ISBN 978-0-8176-3743-9
Sabbagh, Karl, The Riemann hypothesis, Farrar, Straus and Giroux, New York, 2003, ISBN 978-0-374-25007-2, MR 1979664
du Sautoy, Marcus, The music of the primes, HarperCollins Publishers, 2003 [2015-08-23], ISBN 978-0-06-621070-4, MR 2060134, （原始内容存档于2015-09-07）
外部链接[编辑]
查看维基词典中的词条“质数”。
维基教科书中的相关电子教程：小学数学/质数与合数
Hazewinkel, Michiel (编), Prime number, 数学百科全书, Springer, 2001, ISBN 978-1-55608-010-4
Caldwell, Chris, The Prime Pages at primes.utm.edu（页面存档备份，存于互联网档案馆）.
Prime Numbers，In Our Time (BBC Radio 4)（英语：BBC Radio 4）的《In Our Time》节目。
An Introduction to Analytic Number Theory, by Ilan Vardi and Cyril Banderier（页面存档备份，存于互联网档案馆）
Plus teacher and student package: prime numbers（页面存档备份，存于互联网档案馆） from Plus, the free online mathematics magazine produced by the Millennium Mathematics Project at the University of Cambridge.
出现质数实验 （页面存档备份，存于互联网档案馆）
出现可以被整除的机率
质数产生器与计算器[编辑]
Prime Number Checker （页面存档备份，存于互联网档案馆） identifies the smallest prime factor of a number.
Fast Online primality test with factorization（页面存档备份，存于互联网档案馆） makes use of the Elliptic Curve Method (up to thousand-digits numbers, requires Java).
Huge database of prime numbers（页面存档备份，存于互联网档案馆）
Prime Numbers up to 1 trillion （页面存档备份，存于互联网档案馆）
素数发生器和校验器 （页面存档备份，存于互联网档案馆）
查论编和因数有关的整数分类简介
质因数分解
因数
元因数
除数函数
质因数
算术基本定理
依因数分解分类
质数
合数
半素数
普洛尼克数
楔形数
无平方数因数的数
幂数
质数幂
平方数
立方数
次方数
阿喀琉斯数
光滑数
正规数
粗糙数
不寻常数
依因数和分类
完全数
殆完全数
准完全数
多重完全数
Hemiperfect数
Hyperperfect number（英语：Hyperperfect number）
超完全数
元完全数
半完全数
本原半完全数
实际数
有许多因数
过剩数
本原过剩数
高过剩数
超过剩数
可罗萨里过剩数
高合成数
Superior highly composite number（英语：Superior highly composite number）
奇异数
和真因子和数列有关
不可及数
相亲数
交际数
婚约数
其他
亏数
友谊数
孤独数
卓越数
欧尔调和数
佩服数
节俭数
等数位数
奢侈数
规范控制
BNF: cb11932592t (data)
FAST: 1041241
GND: 4047263-2
J9U: 987007538747905171
LCCN: sh85093218
LNB: 000232578
NDL: 00571462
NKC: ph139050
取自“https://zh.wikipedia.org/w/index.php?title=质数&oldid=80711832”
分类：素数整数数列隐藏分类：含有访问日期但无网址的引用的页面CS1英语来源 (en)使用ISBN魔术链接的页面含有英语的条目自2022年7月有未列明来源语句的条目有未列明来源语句的条目包含BNF标识符的维基百科条目包含FAST标识符的维基百科条目包含GND标识符的维基百科条目包含J9U标识符的维基百科条目包含LCCN标识符的维基百科条目包含LNB标识符的维基百科条目包含NDL标识符的维基百科条目包含NKC标识符的维基百科条目
本页面最后修订于2024年1月29日 (星期一) 16:57。
本站的全部文字在知识共享 署名-相同方式共享 4.0协议之条款下提供，附加条款亦可能应用。（请参阅使用条款）
Wikipedia®和维基百科标志是维基媒体基金会的注册商标；维基™是维基媒体基金会的商标。
维基媒体基金会是按美国国内税收法501(c)(3)登记的非营利慈善机构。
隐私政策
关于维基百科
免责声明
行为准则
开发者
统计
Cookie声明
手机版视图
开关有限宽度模式
百度知道 - 信息提示
百度知道 - 信息提示
百度首页
商城
注册
登录
网页
资讯
视频
图片
知道
文库
贴吧采购
地图更多
搜索答案
我要提问
百度知道>提示信息
知道宝贝找不到问题了>_
该问题可能已经失效。返回首页
15秒以后自动返回
帮助
| 意见反馈
| 投诉举报
京ICP证030173号-1 京网文【2023】1034-029号 ©2024Baidu 使用百度前必读 | 知道协议
什么是质数与合数？ - 知乎
什么是质数与合数？ - 知乎切换模式写文章登录/注册什么是质数与合数？易考360管理类联考易考360管理类联考考研辅导什么是质数？什么是合数？1是质数吗？2是合数吗？联考中经常考哪些数？这些看似基础却又经常搞错的数学知识点，常令考生在考试中失分，今天就带大家捋一捋！质数：只有1和它本身两个因数（约数），那么这样的数叫做质数。比如7，只有1和7两个约数。合数：除了能被1和它本身整除，还能被其他的正整数整除，那么这样的数叫做合数。比如8，有1、2、4和8四个约数。所以说，因数个数为2，则是质数；因数个数大于2，则是合数。那“1”因数只有1个，是质数还是合数呢？答案是，既不是质数也不是合数，因为它只有本身一个因数，不符合质数和合数两个定义。在联考中会考啥？怎么考呢？1、30以内的质数：2、3、5、7、11、13、17、19、23、29。2、2是唯一一个偶数质数，且常作为考点！其他质数均是奇数！例：如果两个质数的和或差是奇数，那么其中必有一个数是2！ 如果三个质数之和为偶数，那么其中必有一个数是2！同学们能绕过来吗？接下来让我们看一道例题，联考是怎么考的呢？例：设m、n是小于20的质数，满足条件|m-n|=2的{m，n}共有（ ）。A.2组 B.3组 C.4组 D.5组 E.8组答案解析：C。枚举思维（20以内的质数：2、3、5、7、11、13、17、19），显然，有3,5；5,7；11,13；17,19。共4组，这里要弄清楚3,5和5,3是一样的，集合数数列的区别，有序与无序！若问的是m，n取值有集中情况，则为8种。怎么样，同学们都清楚了吗？编辑于 2022-04-08 11:01数学赞同 5添加评论分享喜欢收藏申请
数论 - 质数与合数 - 知乎
数论 - 质数与合数 - 知乎首发于Tiger爱数学切换模式写文章登录/注册数论 - 质数与合数Tiger数学爱好者，微信公众号“老虎科学探秘”在自然数中有一类数非常特殊，它们叫质数又叫素数。质数指那些大于1的，且除了1和它自身之外再没有其它约数的自然数。合数是指除了1和它自身之外还有其它约数的自然数。自然数1既不是质数也不是合数。100以内的质数有25个，{2、3、5、7、11......}，2是质数中唯一的偶数。质数在自然数的世界中承担着重要的角色，就像元素对于化学或者粒子对于物理一样，从一定的的意义上讲，自然数是由素数构成的。为什么这么讲呢？我们看一下算数基本定理：大于1的自然数n都可以分解成有限个质数的乘积n=p1^a1 x p2^2 x ...x pn^an; p1、p2、......、pn都是质数，a1、a2、......、an都是大于0的自然数。这就是分解质因数，算数基本定理告诉我们两件事：对于任一大于1的自然数，一定可以分解成以上的形式对于任一大于1的自然数，这个分解形式具有唯一性（不计质数的排列次序）质数是不是有限个？当然不是，我们看看欧几里得是怎么证明的：假设质数个数是有限的，有n个，把所有的质数有小到大排列p1、p2、......、pn存在N=p1 x p2 x......x pn +1, N一定大于pn如果N是质数，说明存在一个大于pn的质数N；如果N是合数，那么N一定可以被某个质数整除，但所有的n个质数p1、p2、......、pn都不能整除N，因为它们除N都余1，一定在n个质数之外还有质数，所以假设不成立，质数有无限多个。来个题玩玩：证明存在自然数n，使得n+1、n+2、......、n+2019都是合数。其实只需使得n=2020!+1，那么2020!+2、2020!+3、......、2020!+2020都是合数。这个证明很容易，但结论却很有趣，换句话说，你总可以找到任意多个连续的自然数，它们中都不会出现质数。再来一个：从1~100，任意取一些不同的数相乘使得它们的乘积是平方数，有多少种取法？关\注\公\众\号“老虎科学探秘”后台回复191128，我们来对对答案吧！编辑于 2020-05-06 17:15初等数论小学奥数初中数学赞同 253 条评论分享喜欢收藏申请转载文章被以下专栏收录Tiger
请问什么是质数与合数？什么是奇数与偶数呢？麻烦详细讲一下？ - 知乎
请问什么是质数与合数？什么是奇数与偶数呢？麻烦详细讲一下？ - 知乎首页知乎知学堂发现等你来答切换模式登录/注册数学数论数学证明请问什么是质数与合数？什么是奇数与偶数呢？麻烦详细讲一下？关注者3被浏览1,093关注问题写回答邀请回答好问题添加评论分享2 个回答默认排序雪珂随笔数学家 关注质数也称素数，指的是只能被1和其自身整除的正整数；合数，是若干个（至少2个）素数的乘积，其中包括至少1个大于1的正因子。能被2 整除的自然数为偶数，可表示为2n。不能被2整除的正整数为奇数，可表示为2n+1。发布于 2022-12-06 20:33赞同添加评论分享收藏喜欢收起wyl2928喜爱数字游戏 关注先说说奇数、偶数：奇数即通常所说的“单数”，像1，3，5，7，9……偶数即通常说的“双数”，像0，2，4，6，8……所谓奇、偶也就是单、双。再说质数和合数，质数与合数是相对而言。质数：一个数除了1和本身外，不被任何其他数整除，这个数就是质数；如2，3，5，7，11，13……一个数除了1和本身外，还可以被其他数整除，那么这个数是合数。像4，6，8，9，15，21，25，77……发布于 2023-08-22 15:48赞同 1添加评论分享收藏喜欢收起
质数_百度百科
度百科 网页新闻贴吧知道网盘图片视频地图文库资讯采购百科百度首页登录注册进入词条全站搜索帮助首页秒懂百科特色百科知识专题加入百科百科团队权威合作下载百科APP个人中心质数[zhì shù]播报讨论上传视频数学概念收藏查看我的收藏0有用+10质数是指在大于1的自然数中，除了1和它本身以外不再有其他因数的自然数。中文名质数外文名prime number别 名素数讨论范围非0自然数定 义只有1和它本身两个因数的自然数反义词合数所属范围自然数目录1简介2性质3应用4编程▪基本判断思路▪代码▪素性检测▪筛素数法5猜想▪哥德巴赫猜想▪黎曼猜想▪孪生质数▪梅森质数简介播报编辑质数又称素数。一个大于1的自然数，除了1和它自身外，不能被其他自然数整除的数叫做质数；否则称为合数（规定1既不是质数也不是合数）。质数的个数是无穷的。欧几里得的《几何原本》中有一个经典的证明。它使用了证明常用的方法：反证法。具体证明如下：假设质数只有有限的n个，从小到大依次排列为p1，p2，……，pn，设N=p1×p2×……×pn。如果 为素数，则 要大于p1，p2，……，pn，所以它不在那些假设的素数集合中。如果N+1为合数，因为任何一个合数都可以分解为几个素数的积；而N和N+1的最大公约数是1，所以不可能被p1，p2，……，pn整除，所以该合数分解得到的素因数肯定不在假设的素数集合中。因此无论该数是素数还是合数，都意味着在假设的有限个素数之外还存在着其他素数。所以原先的假设不成立。也就是说，素数有无穷多个。其他数学家给出了一些不同的证明。欧拉证明了全部素数的倒数之和是发散的，恩斯特·库默的证明更为简洁，哈里·弗斯滕伯格则用拓扑学加以证明。尽管整个素数是无穷的，仍然有人会问“100，000以下有多少个素数？”，“一个随机的100位数多大可能是素数？”。素数定理可以回答此问题。性质播报编辑1、质数p的约数只有两个：1和p。2、算术基本定理：任一大于1的自然数，要么本身是质数，要么可以分解为几个质数之积，且这种分解是唯一的。3、质数的个数是无限的。4、质数的个数公式 是不减函数。5、若n为正整数，在 到 之间至少有一个质数。6、若n为大于或等于2的正整数，在n到 之间至少有一个质数。7、在一个大于1的数a和它的2倍之间（即区间（a, 2a]中）必存在至少一个素数。8、存在任意长度的素数等差数列 [1]。 9、任一充分大的偶数都可以表示成一个素数加一个素因子个数不超过2个的数的和，简称为“1+2”。 [2]。应用播报编辑质数被利用在密码学上，所谓的公钥就是将想要传递的信息在编码时加入质数，编码之后传送给收信人，任何人收到此信息后，若没有此收信人所拥有的密钥，则解密的过程中（实为寻找素数的过程），将会因为找质数的过程（分解质因数）过久，使即使取得信息也会无意义。在汽车变速箱齿轮的设计上，相邻的两个大小齿轮齿数设计成质数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强耐用度减少故障。在害虫的生物生长周期与杀虫剂使用之间的关系上，杀虫剂的质数次数的使用也得到了证明。实验表明，质数次数地使用杀虫剂是最合理的：都是使用在害虫繁殖的高潮期，而且害虫很难产生抗药性。以质数形式无规律变化的导弹和鱼雷可以使敌人不易拦截。多数生物的生命周期也是质数（单位为年），这样可以最大程度地减少碰见天敌的机会。编程播报编辑基本判断思路在一般领域，对正整数n，如果用2到 之间的所有整数去除，均无法整除，则n为质数。代码Python 代码：from math import sqrtdef is_prime(n):
if n == 1:
return False
for i in range(2, int(sqrt(n))+1):
if n % i == 0:
return False
return TrueJava代码：1.
public static boolean testIsPrime2(int n){
if (n <= 3) {
return n > 1;
}
for(int i=2;i if(n%i == 0) return false; } return true; } /*优化后*/ public static boolean testIsPrime3(int n){ if (n <= 3) { return n > 1; } for(int i=2;i<=Math.sqrt(n);i++){ if(n%i == 0) return false; } return true; } 2. public class Prime { public static void main（String[] args） { int a = 17; //判断17是不是质数 int c = 0; for (int b = 2; b < a; b++) { if (a % b != 0) { c++; } } if (c == a - 2) { System.out.println(a + "是质数"); } else { System.out.println(a + "不是质数"); } } }Php代码：function isPrime($n) {//TurkHackTeam AVP production if ($n <= 3) { return $n > 1; } else if ($n % 2 === 0 || $n % 3 === 0) { return false; } else { for ($i = 5; $i * $i <= $n; $i += 6) { if ($n % $i === 0 || $n % （$i + 2) === 0） { return false; } } return true; } }C#代码：using System; namespace 计算质数 { class Program { static void Main(string[] args) { for (int i = 2,j=1; i < 2100000000&&j<=1000; i++)//输出21亿内的所有质数，j控制只输出1000个。 { if (st(i)) { Console.WriteLine("{0,-10}{1}",j,i); j++; } } } static bool st(int n)//判断一个数n是否为质数 { int m = (int)Math.Sqrt(n); for(int i=2;i<=m;i++) { if(n%i==0 && i!=n) return false; } return true; } } } C代码：#include #include int main() { double x,y,i; int a,b; x = 3.0; do{ i = 2.0; do{ y = x / i; a = (int)y; if(y != a)//用于判断是否为整数 { if(i == x - 1) { b = (int)x; printf("%d\n",b); } } i++; }while(y != a); x++; }while(x <= 10000.0);//3到10000的素数 system("pause");//防止闪退 return 0; }C/C++代码：#include #include #include using namespace std; const long long size=100000;//修改size的数值以改变最终输出的大小 long long zhishu[size/2]; void work (){//主要程序 zhishu[1]=2; long long k=2; for(long long i=3;i<=size;i++){//枚举每个数 bool ok=1; for(long long j=1;j if(i%zhishu[j]==0){ ok=!ok; break; } } if（ok）{ zhishu[k]=i; cout<<"count"< k++; } } } int main（）{ freopen("zhishu.out","w",stdout); cout<<"count1 2"< work(); return 0; }bool isPrime(unsigned long n) { if (n <= 3) { return n > 1; } else if (n % 2 == 0 || n % 3 == 0) { return false; } else { for (unsigned short i = 5; i * i <= n; i += 6) { if (n % i == 0 || n % （i + 2） == 0) { return false; } } return true; } }Pascal代码：function su(a:longint):boolean; var begin if a=2 then exit(true) else for i:=2 to trunc(sqrt(a))+1 do if a mod i=0 then exit（false）; exit(true); end.Javascript代码：function isPrime(n) { if (n <= 3) { return n > 1; } if (n % 2 == 0 || n % 3 == 0) { return false; } for (var i = 5; i * i <= n; i ++) { if (n % i == 0 || n % (i + 1) == 0) { return false; } } return true; }Go代码：func isPrime(value int) bool { if value <= 3 { return value >= 2 } if value%2 == 0 || value%3 == 0 { return false } for i := 5; i*i <= value; i += 6 { if value%i == 0 || value%（i+2） == 0 { return false } } return true }Basic 代码Private Function IfPrime（ByVal x As Long） As Boolean Dim i As Long If x < 0 Then x = -x If x = 2 Then Return True If x = 1 Then Return True If x = 3 Then Return False If x = 0 Then MsgBox("error",,) Return False End If For i = 2 To Int(Sqrt(x)) Step 1 If x Mod i = 0 Then Return False Next i Return True End FunctionALGOL代码begin Boolean array a[2:100]; integer i,j; for i := 2 step 1 until 100 do a[i] := true; for i := 2 step 1 until 10 do if a[i] then for j := 2 step 1 until 1000÷i do a[i × j] := false; for i := 2 step 1 until 100 do if a[i] then print (i); end 素性检测素性检测一般用于数学或者加密学领域。用一定的算法来确定输入数是否是素数。不同于整数分解，素性测试一般不能得到输入数的素数因子，只说明输入数是否是素数。大整数的分解是一个计算难题，而素性测试是相对更为容易（其运行时间是输入数字大小的多项式关系）。有的素性测试证明输入数字是素数，而其他测试，比如米勒 - 拉宾（Miller–Rabin ）则是证明一个数字是合数。因此，后者可以称为合性测试。素性测试通常是概率测试（不能给出100%正确结果）。这些测试使用除输入数之外，从一些样本空间随机出去的数；通常，随机素性测试绝不会把素数误判为合数，但它有可能为把一个合数误判为素数。误差的概率可通过多次重复试验几个独立值a而减小；对于两种常用的测试中，对任何合数n，至少一半的a检测n的合性，所以k的重复可以减小误差概率最多到 ，可以通过增加k来使得误差尽量小。随机素性测试的基本结构：1、随机选取一个数字a。2、检测某个包含a和输入n的等式（与所使用的测试方法有关）。如果等式不成立，则n是合数，a作为n是合数的证据，测试完成。3、从1步骤重复整个过程直到达到所设定的精确程度。在几次或多次测试之后，如果n没有被判断为合数，那么可以说n可能是素数。常见的检测算法：费马素性检验（Fermat primality test），米勒拉宾测试（Miller–Rabin primality test） ，Solovay–Strassen测试，卢卡斯-莱默检验法（Lucas–Lehmer primality test）。筛素数法筛素数法可以比枚举法节约极大量的时间（定n为所求最大值，m为≤n的质数个数，那么枚举需要O（n^2）的时间复杂度，而筛素数法为O（m*n）,显然m< #include #include #include using namespace std; const long long size=1000000;//修改此值以改变要求到的最大值 bool zhishu[size+5]={false}; int main（）{ freopen（"zhishu.out","w",stdout）;//输出答案至“筛质数（shaizhishu）.exe”所在文件夹内 zhishu[2]=true; for（long long i=3;i<=size;i+=2）zhishu[i]=true;//所有奇数标为true，偶数为false for（long long i=3;i<=size;i++）{ if（zhishu[i]）{//如果i是质数 int cnt=2; while（cnt*i<=size）{//把i的倍数标为false（因为它们是合数） zhishu[cnt*i]=false; cnt++; } } } int cnt=1; for（int i=2;i<=size;i++）{//全部遍历一遍 if（zhishu[i]）{//如果仍然标记为true（是质数）则输出 cout< cnt++; } } return 0; } /* 样例输出结果，第一个数是个数，第二个是第几个质数 1 2 2 3 3 5 4 7 5 11 6 13 7 17 8 19 9 23 10 29 11 31 12 37 13 41 14 43 15 47 16 53 17 59 18 61 19 67 20 71 21 73 22 79 23 83 24 89 25 97 */筛选法的Java实现，如下：/** * @title SOE * @desc 简单的埃氏筛选法计算素数 * @author he11o * @date 2016年5月3日 * @version 1.0 */ public class SOE { public static int calPrime（int n）{ if（n<=1）{ return 0; } byte[] origin = new byte[n+1]; int count = 0; for（int i=2;i if（origin[i] == 0）{ count++; int k = 2; while（i*k<=n）{ origin[i*k] = 1; k++; } }else{ continue; } } return count; } }采用简单的埃氏筛选法和简单的开方判断素数法计算1000000以内素数的个数的效率比较：StopWatch '计算1000000以内素数的个数': running time （millis） = 268-----------------------------------------ms % Task name-----------------------------------------00024 009% 简单的埃氏筛选法；00244 091% 简单的开方判断素数法。猜想播报编辑哥德巴赫猜想：是否每个大于2的偶数都可写成两个素数之和？孪生素数猜想：孪生素数就是差为2的素数对，例如11和13。是否存在无穷多的孪生素数？斐波那契数列内是否存在无穷多的素数？是否有无穷多个的梅森素数？在n2与（n+1）2之间是否每隔n就有一个素数？是否存在无穷个形式如X2+1素数？黎曼猜想 [2]哥德巴赫猜想在1742年给欧拉的信中哥德巴赫提出了以下猜想：任一大于2的整数都可写成两个质数之和。因现今数学界已经不使用“1也是素数”这个约定，原初猜想的现代陈述为：任一大于5的整数都可写成三个质数之和。欧拉在回信中也提出另一等价版本，即任一大于2的偶数想陈述为欧拉的版本。把命题"任一充分大的偶数都可以表示成为一个素因子个数不超过a个的数与另一个素因子不超过b个的数之和"记作"a+b"。1966年陈景润证明了"1+2"成立，即"任一充分大的偶数都可以表示成二个素数的和，或是一个素数和一个半素数的和"。 今日常见的猜想陈述为欧拉的版本，即任一大于2的偶数都可写成两个素数之和，亦称为“强哥德巴赫猜想”或“关于偶数的哥德巴赫猜想”。从关于偶数的哥德巴赫猜想，可推出任一大于7的奇数都可写成三个质数之和的猜想。后者称为“弱哥德巴赫猜想”或“关于奇数的哥德巴赫猜想”。若关于偶数的哥德巴赫猜想是对的，则关于奇数的哥德巴赫猜想也会是对的。1937年时前苏联数学家维诺格拉多夫已经证明充分大的奇质数都能写成三个质数的和，也称为“哥德巴赫-维诺格拉朵夫定理”或“三素数定理”。2013年，秘鲁数学家哈拉尔德·赫尔弗戈特在巴黎高等师范学院宣称：证明了一个“弱哥德巴赫猜想”，即“任何一个大于7的奇数都能被表示成3个奇素数之和”。黎曼猜想黎曼猜想是关于黎曼ζ函数ζ（s）的零点分布的猜想，由数学家波恩哈德·黎曼（1826～1866）于1859年提出。德国数学家希尔伯特列出23个数学问题。其中第8问题中便有黎曼假设。素数在自然数中的分布并没有简单的规律。黎曼发现素数出现的频率与黎曼ζ函数紧密相关。黎曼猜想提出：黎曼ζ函数ζ（s）非平凡零点（在此情况下是指s不为-2、-4、-6等点的值）的实数部份是1/2。即所有非平凡零点都应该位于直线1/2 + ti（“临界线”（critical line））上。t为一实数，而i为虚数的基本单位。无人给出一个令人信服的关于黎曼猜想的合理证明。在黎曼猜想的研究中，数学家们把复平面上 Re（s）=1/2 的直线称为 critical line。 运用这一术语，黎曼猜想也可以表述为：黎曼ζ 函数的所有非平凡零点都位于 critical line 上。黎曼猜想是黎曼在 1859 年提出的。在证明素数定理的过程中，黎曼提出了一个论断：Zeta函数的零点都在直线Res（s） = 1/2上。他在作了一番努力而未能证明后便放弃了，因为这对他证明素数定理影响不大。但这一问题仍然未能解决，甚至于比此假设简单的猜想也未能获证。而函数论和解析数论中的很多问题都依赖于黎曼假设。在代数数论中的广义黎曼假设更是影响深远。若能证明黎曼假设，则可带动许多问题的解决。孪生质数1849年，波林那克提出孪生质数猜想（the conjecture of twin primes），即猜测存在无穷多对孪生质数。猜想中的“孪生质数”是指一对质数，它们之间相差2。例如3和5，5和7，11和13，10,016,957和10,016,959等等都是孪生质数。英国数学家戈弗雷·哈代和约翰·李特尔伍德曾提出一个“强孪生素数猜想”。这一猜想不仅提出孪生素数有无穷多对，而且还给出其渐近分布形式。2013年5月14日，《自然》（Nature）杂志在线报道张益唐证明了“存在无穷多个之差小于7000万的素数对”，这一研究随即被认为在孪生素数猜想这一终极数论问题上取得了重大突破，甚至有人认为其对学界的影响将超过陈景润的“1+2”证明。 [3]梅森质数17世纪还有位法国数学家叫梅森，他曾经做过一个猜想：当2p-1 中的p是质数时，2p-1是质数。他验算出：当p=2、3、5、7、17、19时，所得代数式的值都是质数，后来，欧拉证明p=31时，2p-1是质数。 p=2，3，5，7时，2p-1都是素数，但p=11时，所得2,047=23×89却不是素数。梅森去世250年后，美国数学家科尔证明，267-1=193,707,721×761,838,257,287，是一个合数。这是第九个梅森数。20世纪，人们先后证明：第10个梅森数是质数，第11个梅森数是合数。由于这种质数珍奇而迷人，它被人们称为“数学珍宝”。值得一提的是，中国数学家和语言学家周海中根据已知的梅森质数及其排列，巧妙地运用联系观察法和不完全归纳法，于1992年正式提出了梅森素质分布的猜想，这一重要猜想被国际上称为“周氏猜测”。新手上路成长任务编辑入门编辑规则本人编辑我有疑问内容质疑在线客服官方贴吧意见反馈投诉建议举报不良信息未通过词条申诉投诉侵权信息封禁查询与解封©2024 Baidu 使用百度前必读 | 百科协议 | 隐私政策 | 百度百科合作平台 | 京ICP证030173号 京公网安备110000020000 质数 - 维基百科，自由的百科全书 跳转到内容 主菜单 主菜单 移至侧栏 隐藏 导航 首页分类索引特色内容新闻动态最近更改随机条目资助维基百科 帮助 帮助维基社群方针与指引互助客栈知识问答字词转换IRC即时聊天联络我们关于维基百科 搜索 搜索 创建账号 登录 个人工具 创建账号 登录 未登录编辑者的页面 了解详情 贡献讨论 目录 移至侧栏 隐藏 序言 1定义和例子 2算术基本定理 开关算术基本定理子章节 2.11是否为质数 3历史 4素数的数目 开关素数的数目子章节 4.1欧几里得的证明 4.2欧拉的解析证明 5测试质数与整数分解 开关测试质数与整数分解子章节 5.1试除法 5.2筛法 5.3质数测试与质数证明 5.4专用目的演算法与最大已知质数 5.5整数分解 6质数分布 开关质数分布子章节 6.1质数的公式 6.2一特定数以下的质数之数量 6.3等差数列 6.4二次多项式的质数值 7未解决的问题 开关未解决的问题子章节 7.1ζ函数与黎曼猜想 7.2其他猜想 8应用 开关应用子章节 8.1模一质数与有限体之运算 8.2其他数学里出现的质数 8.3公开金钥加密 8.4自然里的质数 9推广 开关推广子章节 9.1环内的素元 9.2质理想 9.3赋值 10在艺术与文学里 11另见 12注记 13参考资料 14外部链接 开关外部链接子章节 14.1质数产生器与计算器 开关目录 质数 136种语言 AfrikaansAlemannischAragonésÆngliscالعربيةالدارجةمصرىঅসমীয়াAsturianuAzərbaycancaتۆرکجهБашҡортсаŽemaitėškaБеларускаяБеларуская (тарашкевіца)БългарскиবাংলাBrezhonegBosanskiCatalàکوردیČeštinaЧӑвашлаCymraegDanskDeutschZazakiΕλληνικάEmiliàn e rumagnòlEnglishEsperantoEspañolEestiEuskaraفارسیSuomiVõroNa Vosa VakavitiFøroysktFrançaisNordfriiskGaeilge贛語Kriyòl gwiyannenGalegoગુજરાતીHawaiʻiעבריתहिन्दीHrvatskiHornjoserbsceKreyòl ayisyenMagyarՀայերենԱրեւմտահայերէնInterlinguaBahasa IndonesiaÍslenskaItaliano日本語PatoisLa .lojban.JawaქართულიҚазақшаភាសាខ្មែរಕನ್ನಡ한국어KurdîKernowekКыргызчаLatinaLëtzebuergeschLimburgsLombardLietuviųLatviešuМакедонскиമലയാളംМонголमराठीBahasa MelayuMaltiမြန်မာဘာသာPlattdüütschनेपालीNederlandsNorsk nynorskNorsk bokmålOccitanଓଡ଼ିଆਪੰਜਾਬੀPolskiPiemontèisپنجابیPortuguêsRomânăРусскийСаха тылаSicilianuSrpskohrvatski / српскохрватскиTaclḥitසිංහලSimple EnglishSlovenčinaSlovenščinaSoomaaligaShqipСрпски / srpskiSvenskaKiswahiliŚlůnskiதமிழ்తెలుగుТоҷикӣไทยTagalogTürkçeئۇيغۇرچە / UyghurcheУкраїнськаاردوOʻzbekcha / ўзбекчаVènetoVepsän kel’Tiếng ViệtWest-VlamsWalonWinaray吴语ХальмгייִדישYorùbáⵜⴰⵎⴰⵣⵉⵖⵜ ⵜⴰⵏⴰⵡⴰⵢⵜ文言Bân-lâm-gú粵語 编辑链接 条目讨论 简体 不转换简体繁體大陆简体香港繁體澳門繁體大马简体新加坡简体臺灣正體 阅读编辑查看历史 工具 工具 移至侧栏 隐藏 操作 阅读编辑查看历史 常规 链入页面相关更改上传文件特殊页面固定链接页面信息引用本页获取短URL下载二维码维基数据项目 打印/导出 下载为PDF可打印版 在其他项目中 维基共享资源 维基百科，自由的百科全书 各种各样的数 基本 N ⊆ Z ⊆ Q ⊆ R ⊆ C {\displaystyle \mathbb {N} \subseteq \mathbb {Z} \subseteq \mathbb {Q} \subseteq \mathbb {R} \subseteq \mathbb {C} } 正数 R + {\displaystyle \mathbb {R} ^{+}} 自然数 N {\displaystyle \mathbb {N} } 正整数 Z + {\displaystyle \mathbb {Z} ^{+}} 小数 有限小数 无限小数 循环小数 有理数 Q {\displaystyle \mathbb {Q} } 代数数 A {\displaystyle \mathbb {A} } 实数 R {\displaystyle \mathbb {R} } 复数 C {\displaystyle \mathbb {C} } 高斯整数 Z [ i ] {\displaystyle \mathbb {Z} [i]} 负数 R − {\displaystyle \mathbb {R} ^{-}} 整数 Z {\displaystyle \mathbb {Z} } 负整数 Z − {\displaystyle \mathbb {Z} ^{-}} 分数 单位分数 二进分数 规矩数 无理数 超越数 虚数 I {\displaystyle \mathbb {I} } 二次无理数 艾森斯坦整数 Z [ ω ] {\displaystyle \mathbb {Z} [\omega ]} 延伸 二元数 四元数 H {\displaystyle \mathbb {H} } 八元数 O {\displaystyle \mathbb {O} } 十六元数 S {\displaystyle \mathbb {S} } 超实数 ∗ R {\displaystyle ^{*}\mathbb {R} } 大实数 上超实数 双曲复数 双复数 复四元数 共四元数（英语：Dual quaternion） 超复数 超数 超现实数 其他 质数 P {\displaystyle \mathbb {P} } 可计算数 基数 阿列夫数 同馀 整数数列 公称值 规矩数 可定义数 序数 超限数 p进数 数学常数 圆周率 π = 3.14159265 {\displaystyle \pi =3.14159265} … 自然对数的底 e = 2.718281828 {\displaystyle e=2.718281828} … 虚数单位 i = − 1 {\displaystyle i={\sqrt {-{1}}}} 无限大 ∞ {\displaystyle \infty } 查论编 质数（Prime number），又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。大于1的自然数若不是质数，则称之为合数（也称为合成数）。例如，5是个质数，因为其正因数只有1与5。7是个质数，因为其正因数只有1与7。而4则是个合数，因为除了1与4外，2也是其正因数。6也是个合数，因为除了1与6外，2与3也是其正因数。算术基本定理确立了质数于数论里的核心地位：任何大于1的整数均可被表示成一串唯一质数之乘积。为了确保该定理的唯一性，1被定义为不是质数，因为在因式分解中可以有任意多个1（如3、1×3、1×1×3等都是3的有效因数分解）。 古希腊数学家欧几里得于公元前300年前后证明有无限多个质数存在（欧几里得定理）。现时人们已发现多种验证质数的方法。其中试除法比较简单，但需时较长：设被测试的自然数为 n {\displaystyle n} ，使用此方法者需逐一测试2与 n {\displaystyle {\sqrt {n}}} 之间的质数，确保它们无一能整除 n {\displaystyle n} 。对于较大或一些具特别形式（如梅森数）的自然数，人们通常使用较有效率的演算法测试其是否为质数（例如282589933-1是直至2018年12月为止已知最大的梅森质数[1]，也是直至2018年12月为止已知最大的质数）。虽然人们仍未发现可以完全区别质数与合数的公式，甚至研究质数分布时相当有力的筛法也会碰到奇偶性问题（也就是多种筛法都无法区别质数跟两个质数相乘的合数的问题），但已建构了质数的分布模式（亦即质数在大数时的统计模式）。19世纪晚期得到证明的质数定理指出：一个任意自然数n为质数的机率反比于其数位（或 n {\displaystyle n} 的对数）。 许多有关质数的问题依然未解，如哥德巴赫猜想（每个大于2的偶数可表示成两个素数之和）及孪生质数猜想（存在无穷多对相差2的质数）。这些问题促进了数论各个分支的发展，主要在于数字的解析或代数方面。质数被用于资讯科技里的几个程序中，如公钥加密利用了难以将大数分解成其质因数之类的性质。质数亦在其他数学领域里形成了各种广义化的质数概念，主要出现在代数里，如质元素及质理想。 定义和例子[编辑] 一个自然数（如1、2、3、4、5、6等）若恰有两个正因数（1及此数本身），则称之为质数[2]。大于1的自然数若不是质数，则称之为合数。 数字12不是质数，因为将12以每4个分成1组，恰可分成3组（也有其他分法）。11则无法分成数量都大于1且都相同的各组，而都会有剩馀。因此，11为质数。 在数字1至6间，数字2、3与5为质数，1、4与6则不是质数。1不是质数，其理由见下文。2是质数，因为只有1与2可整除该数。接下来，3亦为质数，因为1与3可整除3，3除以2会馀1。因此，3为质数。不过，4是合数，因为2是另一个（除1与4外）可整除4的数： 4 = 2 · 2 5又是个质数：数字2、3与4均不能整除5。接下来，6会被2或3整除，因为 6 = 2 · 3 因此，6不是质数。右图显示12不是质数：12 = 3 · 4。不存在大于2的偶数为质数，因为依据定义，任何此类数字 n {\displaystyle n} 均至少有三个不同的因数，即1、2与 n {\displaystyle n} 。这意指 n {\displaystyle n} 不是质数。因此，“奇质数”系指任何大于2的质数。类似地，当使用一般的十进位制时，所有大于5的质数，其尾数均为1、3、7或9，因为尾数0、2、4、6、8为2的倍数，尾数为0或5的数字为5的倍数。 若 n {\displaystyle n} 为一自然数，则1与 n {\displaystyle n} 会整除 n {\displaystyle n} 。因此，质数的条件可重新叙述为：一个数字为质数，若该数大于1，且没有 2 , 3 , … , n − 1 {\displaystyle 2,3,\ldots ,n-1} 会整除 n {\displaystyle n} 。另一种叙述方式为：一数 n > 1 {\displaystyle n>1} 为质数，若不能写成两个整数 a {\displaystyle a} 与 b {\displaystyle b} 的乘积，其中这两数均大于1： n = a ⋅ b {\displaystyle n=a\cdot b} . 换句话说， n {\displaystyle n} 为质数，若 n {\displaystyle n} 无法分成数量都大于1且都相同的各组。 由所有质数组成之集合通常标记为P或 P {\displaystyle \mathbb {P} } 。 前168个质数（所有小于1000的质数）为2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, ...（OEIS数列A000040）。 算术基本定理[编辑] 主条目：算术基本定理 质数对于数论与一般数学的重要性来自于“算术基本定理”。该定理指出，每个大于1的整数均可写成一个以上的质数之乘积，且除了质因数的排序不同外是唯一的[3]。质数可被认为是自然数的“基本建材”，例如： 23244 = 2 · 2 · 3 · 13 · 149 = 22 · 3 · 13 · 149. （22表示2的平方或2次方。） 如同此例一般，相同的因数可能出现多次。一个数n的分解： n = p 1 ⋅ p 2 ⋅ … ⋅ p t {\displaystyle n=p_{1}\cdot p_{2}\cdot \ldots \cdot p_{t}} 成（有限多个）质因数 p 1 {\displaystyle p_{1}} 、 p 2 {\displaystyle p_{2}} 、……、 p t {\displaystyle p_{t}} ，称之为 n {\displaystyle n} 的“因数分解”。算术基本定理可以重新叙述为，任一质数分解除了因数的排序外，都是唯一的。因此，尽管实务上存在许多质数分解演算法来分解较大的数字，但最后都会得到相同的结果。 若 p {\displaystyle p} 为质数，且 p {\displaystyle p} 可整除整数的乘积 a b {\displaystyle ab} ，则 p {\displaystyle p} 可整除 a {\displaystyle a} 或可整除 b {\displaystyle b} 。此一命题被称为欧几里得引理[4]，被用来证明质数分解的唯一性。 1是否为质数[编辑] 最早期的希腊人甚至不将1视为是一个数字[5]，因此不会认为1是质数。到了中世纪与文艺复兴时期，许多数学家将1纳入作为第一个质数[6]。到18世纪中期，克里斯蒂安·哥德巴赫在他与李昂哈德·欧拉著名的通信里将1列为第一个质数，但欧拉不同意[7]。然而，到了19世纪，仍有许多数学家认为数字1是个质数。例如，德里克·诺曼·雷默（Derrick Norman Lehmer）在他那最大达10,006,721的质数列表[8]中，将1列为第1个质数[9]。昂利·勒贝格据说是最后一个称1为质数的职业数学家[10]。到了20世纪初，数学家开始认为1不是个质数，但反而作为“单位”此一特殊类别[6]。 许多数学成果在称1为质数时，仍将有效，但欧几里何的算术基本定理（如上所述）则无法不重新叙述而仍然成立。例如，数字15可分解成3 · 5及 1 · 3 · 5；若1被允许为一个质数，则这两个表示法将会被认为是将15分解至质数的不同方法，使得此一定理的陈述必须被修正。同样地，若将1视为质数，埃拉托斯特尼筛法将无法正常运作：若将1视为质数，此一筛法将会排除掉所有1的倍数（即所有其他的数），只留下数字1。此外，质数有几个1所没有的性质，如欧拉函数的对应值，以及除数函数的总和[11][12]。 历史[编辑] 埃拉托斯特尼筛法是个找出在一特定整数以下的所有质数之简单演算法，由古希腊数学家埃拉托斯特尼于公元前3世纪发明。 在古埃及人的幸存纪录中，有迹象显示他们对质数已有部分认识：例如，在莱因德数学纸草书中的古埃及分数展开时，对质数与对合数有著完全不同的类型。不过，对质数有过具体研究的最早幸存纪录来自古希腊。公元前300年左右的《几何原本》包含与质数有关的重要定理，如有无限多个质数，以及算术基本定理。欧几里得亦展示如何从梅森质数建构出完全数。埃拉托斯特尼提出的埃拉托斯特尼筛法是用来计算质数的一个简单方法，虽然今天使用电脑发现的大质数无法使用这个方法找出。 希腊之后，到17世纪之前，质数的研究少有进展。1640年，皮埃尔·德·费马叙述了费马小定理（之后才被莱布尼茨与欧拉证明）。费马亦推测，所有具 2 2 n + 1 {\displaystyle 2^{2^{n}}+1} 形式的数均为质数（称之为费马数），并验证至 n = 4 {\displaystyle n=4} （即216 + 1）不过，后来由欧拉发现，下一个费马数232 + 1即为合数，且实际上其他已知的费马数都不是质数。法国修道士马兰·梅森发现有的质数具 2 p − 1 {\displaystyle 2^{p}-1} 的形式，其中 p {\displaystyle p} 为质数。为纪念他的贡献，此类质数后来被称为梅森质数。 欧拉在数论中的成果，许多与质数有关。他证明无穷级数 1 2 + 1 3 + 1 5 + 1 7 + 1 11 + … {\displaystyle {\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+{\frac {1}{11}}+\ldots } 会发散。1747年，欧拉证明每个偶完全数都确实为 2 p − 1 ( 2 p − 1 ) {\displaystyle 2^{p-1}(2^{p}-1)} 的形式，其中第二个因数为梅森质数。 19世纪初，勒壤得与高斯独立推测，当 x {\displaystyle x} 趋向无限大时，小于 x {\displaystyle x} 的质数数量会趋近于 x ln x {\displaystyle {\frac {x}{\ln x}}} ，其中 ln x {\displaystyle \ln x} 为 x {\displaystyle x} 的自然对数。黎曼于1859年有关ζ函数的论文（英语：On the Number of Primes Less Than a Given Magnitude）中勾勒出一个程式，导出了质数定理的证明。其大纲由雅克·阿达马与夏尔-让·德拉瓦莱·普桑所完成，他们于1896年独立证明出质数定理。 证明一个大数是否为质数通常无法由试除法来达成。许多数学家已研究过大数的质数测试，通常局限于特定的数字形式。其中包括费马数的贝潘测试（英语：Pépin's test）（1877年）、普罗丝定理（约1878年）、卢卡斯-莱默质数判定法（1856年起）[13]及广义卢卡斯质数测试（英语：Lucas primality test）。较近期的演算法，如APRT-CL（英语：Adleman–Pomerance–Rumely primality test）、ECPP（英语：Elliptic curve primality）及AKS等，均可作用于任意数字上，但仍慢上许多。 长期以来，质数被认为在纯数学以外的地方只有极少数的应用[14]。到了1970年代，发明公共密钥加密这个概念之后，情况改变了，质数变成了RSA加密演算法等一阶演算法之基础。 自1951年以来，所有已知最大的质数都由电脑所发现。对更大质数的搜寻已在数学界以外的地方产生出兴趣。网际网路梅森质数大搜索及其他用来寻找大质数的分散式运算计画变得流行，在数学家仍持续与质数理论奋斗的同时。 素数的数目[编辑] 主条目：欧几里得定理 存在无限多个质数。另一种说法为，质数序列 2, 3, 5, 7, 11, 13, ... 永远不会结束。此一陈述被称为“欧几里得定理”，以古希腊数学家欧几里得为名，因为他提出了该陈述的第一个证明。已知存在其他更多的证明，包括欧拉的分析证明、哥德巴赫依据费马数的证明[15]、弗斯滕伯格使用一般拓扑学的证明[16]，以及库默尔优雅的证明[17]。 欧几里得的证明[编辑] 欧几里得的证明[18]取任一个由质数所组成的有限集合 S {\displaystyle S} 。该证明的关键想法为考虑 S {\displaystyle S} 内所有质数相乘后加一的一个数字： N = 1 + ∏ p ∈ S p {\displaystyle N=1+\prod _{p\in S}p} 。 如同其他自然数一般， N {\displaystyle N} 可被至少一个质数整除（即使N本身为质数亦同）。 任何可整除N的质数都不可能是有限集合 S {\displaystyle S} 内的元素（质数），因为后者除N都会馀1。所以， N {\displaystyle N} 可被其他质数所整除。因此，任一个由质数所组成的有限集合，都可以扩展为更大个由质数所组成之集合。 这个证明通常会被错误地描述为，欧几里得一开始假定一个包含所有质数的集合，并导致矛盾；或者是，该集合恰好包含n个最小的质数，而不任意个由质数所组成之集合[19]。今日， n {\displaystyle n} 个最小质数相乘后加一的一个数字，被称为第 n {\displaystyle n} 个欧几里得数。 欧拉的解析证明[编辑] 欧拉的证明使用到质数倒数的总和 S ( p ) = 1 2 + 1 3 + 1 5 + 1 7 + ⋯ + 1 p {\displaystyle S(p)={\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+\cdots +{\frac {1}{p}}} 。 当 p {\displaystyle p} 够大时，该和会大于任意实数[20]。这可证明，存在无限多个质数，否则该和将只会增长至达到最大质数 p {\displaystyle p} 为止。 S ( p ) {\displaystyle S(p)} 的增加率可使用梅滕斯第二定理来量化[21]。比较总和 1 1 2 + 1 2 2 + 1 3 2 + ⋯ + 1 n 2 = ∑ i = 1 n 1 i 2 {\displaystyle {\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+{\frac {1}{3^{2}}}+\cdots +{\frac {1}{n^{2}}}=\sum _{i=1}^{n}{\frac {1}{i^{2}}}} 当 n {\displaystyle n} 趋向无限大时，此和不会变成无限大（见巴塞尔问题）。这意味著，质数比自然数的平方更常出现。布朗定理指出，孪生质数倒数的总和 ( 1 3 + 1 5 ) + ( 1 5 + 1 7 ) + ( 1 11 + 1 13 ) + ⋯ = ∑ p prime, p + 2 prime ( 1 p + 1 p + 2 ) , {\displaystyle \left({{\frac {1}{3}}+{\frac {1}{5}}}\right)+\left({{\frac {1}{5}}+{\frac {1}{7}}}\right)+\left({{\frac {1}{11}}+{\frac {1}{13}}}\right)+\cdots =\sum \limits _{\begin{smallmatrix}p{\text{ prime, }}\\p+2{\text{ prime}}\end{smallmatrix}}{\left({{\frac {1}{p}}+{\frac {1}{p+2}}}\right)},} 是有限的。 测试质数与整数分解[编辑] 确认一个数 n {\displaystyle n} 是否为质数有许多种方法。最基本的程序为试除法，但因为速率很慢，没有什么实际用处。有一类现代的质数测试可适用于任意数字之上，另有一类更有效率的测试方法，则只能适用于特定的数字之上。大多数此类方法只能辨别 n {\displaystyle n} 是否为质数。也能给出 n {\displaystyle n} 的一个（或全部）质因数之程序称之为因数分解演算法。 试除法[编辑] 主条目：试除法 测试 n {\displaystyle n} 是否为质数的最基本方法为试除法。此一程序将n除以每个大于1且小于等于 n {\displaystyle n} 的平方根之整数 m {\displaystyle m} 。若存在一个相除为整数的结果，则 n {\displaystyle n} 不是质数；反之则是个质数。实际上，若 n = a b {\displaystyle n=ab} 是个合数（其中 a {\displaystyle a} 与 b ≠ 1 {\displaystyle b\neq 1} ），则其中一个因数 a {\displaystyle a} 或 b {\displaystyle b} 必定至大为 n {\displaystyle {\sqrt {n}}} 。例如，对 n = 37 {\displaystyle n=37} 使用试除法，将37除以 m = 2 , 3 , 4 , 5 , 6 {\displaystyle m=2,3,4,5,6} ，没有一个数能整除37，因此37为质数。此一程序若能知道直至 n {\displaystyle {\sqrt {n}}} 的所有质数列表，则可以只检查 m {\displaystyle m} 为质数的状况，以提升效率。例如，为检查37是否为质数，只有3个相除是必要的（ m = 2 , 3 , 5 {\displaystyle m=2,3,5} ），因为4与6为合数。 作为一个简单的方法，试除法在测试大整数时很快地会变得不切实际，因为可能的因数数量会随著n的增加而迅速增加。依据下文所述之质数定理，小于 n {\displaystyle {\sqrt {n}}} 的质数之数量约为 n ln n {\displaystyle {\frac {\sqrt {n}}{\ln {\sqrt {n}}}}} ，因此使用试除法测试 n {\displaystyle n} 是否为质数时，大约会需要用到这么多的数字。对 n = 10 20 {\displaystyle n=10^{20}} ，此一数值约为4.5亿，对许多实际应用而言都太过庞大。 筛法[编辑] 一个能给出某个数值以下的所有质数之演算法，称之为质数筛法，可用于只使用质数的试除法内。最古老的一个例子为埃拉托斯特尼筛法（见上文），至今仍最常被使用。阿特金筛法为另外一例。在电脑出现之前，筛法曾被用来给出107以下的质数列表[22]。 质数测试与质数证明[编辑] 主条目：素性测试 现代测试一般的数字 n {\displaystyle n} 是否为质数的方法可分成两个主要类型，随机（或“蒙特卡洛”）与确定性演算法。确定性演算法可肯定辨别一个数字是否为质数。例如，试除法即是个确定性演算法，因为若正确执行，该方法总是可以辨别一个质数为质数，一个合数为合数。随机演算法一般比较快，但无法完全证明一个数是否为质数。这类测试依靠部分随机的方法来测试一个给定的数字。例如，一测试在应用于质数时总是会通过，但在应用于合数时通过的机率为 p {\displaystyle p} 。若重复这个测试 n {\displaystyle n} 次，且每次都通过，则该数为合数的机率为 1 ( 1 − p ) n {\displaystyle {\frac {1}{(1-p)^{n}}}} ，会随著测试次数呈指数下滑，因此可越来越确信（虽然总是无法完全确信）该数为质数。另一方面，若测试曾失败过，则可知该数为合数。 随机测试的一个特别简单的例子为费马质数判定法，使用到对任何整数 a {\displaystyle a} ， n p ≡ n ( mod p ) {\displaystyle n^{p}\equiv n(\mod p)} ，其中 p {\displaystyle p} 为质数的这个事实（费马小定理）。若想要测试一个数字 b {\displaystyle b} 是否为质数，则可随机选择 n {\displaystyle n} 来计算 n b ( mod b ) {\displaystyle n^{b}(\mod b)} 的值。这个测试的缺点在于，有些合数（卡迈克尔数）即使不是质数，也会符合费马恒等式，因此这个测试无法辨别质数与卡迈克尔数，最小的三个卡迈克尔数为561，1105，1729。卡迈克尔数比质数还少上许多，所以这个测试在实际应用上还是有用的。费马质数判定法更强大的延伸方法，包括贝利-PSW、米勒-拉宾与Solovay-Strassen质数测试，都保证至少在应用于合数时，有部分时候会失败。 确定性演算法不会将合数错误判定为质数。在实务上，最快的此类方法为椭圆曲线质数证明。其运算时间是透过实务分析出来的，不像最新的AKS质数测试，有已被严格证明出来的复杂度。确定性演算法通常较随机演算法来得慢，所以一般会先使用随机演算法，再采用较费时的确定性演算法。 下面表格列出一些质数测试。运算时间以被测试的数字 n {\displaystyle n} 来表示，并对随机演算法，以 k {\displaystyle k} 表示其测试次数。此外， ε {\displaystyle \varepsilon } 是指一任意小的正数， log {\displaystyle \log } 是指一无特定基数的对数。大O符号表示，像是在椭圆曲线质数证明里，所需之运算时间最长为一常数（与n无关，但会与ε有关）乘于log5+ε(n)。 测试 发明于 类型 运算时间 注记 AKS质数测试 2002 确定性 O ( log 6 + ε ( n ) ) {\displaystyle O(\log ^{6+\varepsilon }(n))} 椭圆曲线质数证明 1977 确定性 O ( log 5 + ε ( n ) ) {\displaystyle O(\log ^{5+\varepsilon }(n))} “实务分析” 贝利-PSW质数测试 1980 随机 O ( log 3 n ) {\displaystyle O(\log ^{3}n)} 无已知反例 米勒-拉宾质数判定法 1980 随机 O ( k ⋅ log 2 + ε ( n ) ) {\displaystyle O(k\cdot \log ^{2+\varepsilon }(n))} 错误机率 4 − k {\displaystyle 4^{-k}} Solovay-Strassen质数 1977 随机 O ( k ⋅ log 3 n ) {\displaystyle O(k\cdot \log ^{3}n)} 错误机率 2 − k {\displaystyle 2^{-k}} 费马质数判定法 随机 O ( k ⋅ log 2 + ε ( n ) ) {\displaystyle O(k\cdot \log ^{2+\varepsilon }(n))} 遇到卡迈克尔数时会失败 专用目的演算法与最大已知质数[编辑] 更多信息：质数列表 建构正五边形。5是个费马质数。 除了前述可应用于任何自然数n之上的测试外，一些更有效率的质数测试适用于特定数字之上。例如，卢卡斯质数测试需要知道n − 1的质因数，而卢卡斯-莱默质数测试则需要以n + 1的质因数作为输入。例如，这些测试可应用在检查 n! ± 1 = 1 · 2 · 3 · ... · n ± 1 是否为一质数。此类形式的质数称之为阶乘质数。其他具p+1或p-1之类形式的质数还包括索菲·热尔曼质数（具2p+1形式的质数，其中p为质数）、质数阶乘质数、费马质数与梅森质数（具2p − 1形式的质数，其中p为质数）。卢卡斯-雷默质数测试对这类形式的数特别地快。这也是为何自电脑出现以来，最大已知质数总会是梅森质数的原因。 费马质数具下列形式 Fk = 22k + 1, 其中，k为任意自然数。费马质数以皮埃尔·德·费马为名，他猜想此类数字Fk均为质数。费马认为Fk均为质数的理由为此串列的前5个数字（3、5、17、257及65537）为质数。不过，F5却为合数，且直至2015年发现的其他费马数字也全都是合数。一个正n边形可用尺规作图，若且唯若 n = 2i · m 其中，m为任意个不同费马质数之乘积，及i为任一自然数，包括0。 下列表格给出各种形式的最大已知质数。有些质数使用分散式计算找到。2009年，网际网路梅森质数大搜索因为第一个发现具至少1,000万个数位的质数，而获得10万美元的奖金[23]。电子前哨基金会亦为具至少1亿个数位及10亿个数位的质数分别提供15万美元及25万美元的奖金[24]。 类型 质数 数位 日期 发现者 梅森质数 282589933 − 1 23,249,425 2018年12月21日 网际网路梅森质数大搜索 非梅森质数（普罗斯数） 19,249×213,018,586 + 1 3,918,990 2007年3月26日 十七或者破产 阶乘质数 150209! + 1 712,355 2011年10月 PrimeGrid[25] 质数阶乘质数 1098133# - 1 476,311 2012年3月 PrimeGrid[26] 孪生质数s 3756801695685×2666669 ± 1 200,700 2011年12月 PrimeGrid[27] 整数分解[编辑] 主条目：整数分解 给定一合数n，给出一个（或全部）质因数的工作称之为n的因数分解。椭圆曲线分解是一个依靠椭圆曲线上的运算来分解质因数的演算法。 质数分布[编辑] 1975年，数论学家唐·察吉尔评论质数 像生长于自然数间的杂草，似乎不服从机率之外的法则，（但又）表现出惊人的规律性，并有规范其行为之法则，且以军事化的精准度遵守著这些法则[28]。 大质数的分布，如在一给定数值以下有多少质数这个问题，可由质数定理所描述；但有效描述第n个质数的公式则仍未找到。 存在任意长的连续非质数数列，如对每个正整数 n {\displaystyle n} ，从 ( n + 1 ) ! + 2 {\displaystyle (n+1)!+2} 至 ( n + 1 ) ! + n + 1 {\displaystyle (n+1)!+n+1} 的 n {\displaystyle n} 个连续正整数都会是合数（因为若 k {\displaystyle k} 为2至 n + 1 {\displaystyle n+1} 间的一整数， ( n + 1 ) ! + k {\displaystyle (n+1)!+k} 就可被k整除）。 狄利克雷定理表示，取两个互质的整数a与b，其线性多项式 p ( n ) = a + b n {\displaystyle p(n)=a+bn\,} 会有无限多个质数值。该定理亦表示，这些质数值的倒数和会发散，且具有相同b的不同多项式会有差不多相同的质数比例。 有关二次多项式的相关问题则尚无较好之理解。 质数的公式[编辑] 主条目：质数公式 对于质数，还没有一个已知的有效公式。例如，米尔斯定理与赖特所提的一个定理表示，存在实常数A>1与μ，使得 ⌊ A 3 n ⌋ and ⌊ 2 … 2 2 μ ⌋ {\displaystyle \left\lfloor A^{3^{n}}\right\rfloor {\text{ and }}\left\lfloor 2^{\dots ^{2^{2^{\mu }}}}\right\rfloor } 对任何自然数n而言，均为质数。其中， ⌊ − ⌋ {\displaystyle \lfloor -\rfloor } 为高斯符号，表示不大于符号内数字的最大整数。第二个公式可使用伯特兰-切比雪夫定理得证（由切比雪夫第一个证得）。该定理表示，总是存在至少一个质数p，使得 n < p < 2n − 2，其中n为大于3的任一自然数。第一个公式可由威尔逊定理导出，每个不同的n会对应到不同的质数，除了数字2会有多个n对应到外。不过，这两个公式都需要先计算出A或μ的值来[29]。 不存在一个只会产生质数值的非常数多项式，即使该多项式有许多个变数。不过，存在具9个变数的丢番图方程，其参数具备以下性质：该参数为质数，若且唯若其方程组有自然数解。这可被用来获得其所有“正值”均为质数的一个公式[30]。 一特定数以下的质数之数量[编辑] 主条目：质数定理和质数计算函数 图中的曲线分别表示π(n)（蓝）、n / ln (n)（绿）与Li(n)（红）。 质数计算函数π(n)被定义为不大于n的质数之数量。例如，π(11) = 5，因为有5个质数小于或等于11。已知有演算法可比去计算每个不大于n的质数更快的速率去计算π(n)的值。质数定理表示，π(n)的可由下列公式近似给出： π ( n ) ≈ n ln n , {\displaystyle \pi (n)\approx {\frac {n}{\ln n}},} 亦即，π(n)与等式右边的值在n趋近于无限大时，会趋近于1。这表示，小于n的数字为质数的可能性（大约）与n的数位呈正比。对π(n)更精确的描述可由对数积分给出： Li ( n ) = ∫ 2 n d t ln t {\displaystyle \operatorname {Li} (n)=\int _{2}^{n}{\frac {dt}{\ln t}}} 。 质数定理亦蕰涵著对第n个质数pn（如p1 = 2、p2 = 3等）的大小之估算：当数字大到某一程度时，pn的值会变得约略为n log(n)[31]。特别的是，质数间隙，即两个连续质数pn与pn+1间的差会变得任意地大。后者可由数列 n! + 2, n! + 3,…, n! + n（其中n为任一自然数）看出。 等差数列[编辑] 等差数列是指由被一固定数（模）q除后会得到同一馀数的自然数所组成之集合。例如： 3, 12, 21, 30, 39, ..., 是一个等差数列，模q = 9。除了3以外，其中没有一个数会是质数，因为3 + 9n = 3(1 + 3n)，所以此一数列里的其他数字均为合数。（一般来所有大于q的质数都具有q#·n + m的形式，其中0 < m < q#，且m没有不大于q的质因数。）因此，数列 a, a + q, a + 2q, a + 3q,… 只在a与q 互质（其最大公因数为1）之时，可以有无限多个质数。若满足此一必要条件，狄利克雷定理表示，该数列含有无限多个质数。下图描述q = 9时的情形：数字每遇到9的倍数就会再再由下往上缠一次。质数以红底标记。行（数列）开始于a = 3, 6, 9者至多只包含一个质数。其他行（a = 1, 2, 4, 5, 7, 8）则均包含无限多个质数。更甚之，质数以长期来看，会均匀分布于各行之中，亦即每个质数模9会与6个数其中一数同馀的机率均为1/6。 质数（以红底标计）在模9的等差数列中。 格林-陶定理证明，存在由任意多个质数组成的等差数列[32]。一个奇质数p可表示成两个平方数之和p = x2 + y2，若且唯若p同馀于1模4（费马平方和定理）。 二次多项式的质数值[编辑] 乌岚螺旋。红点表示质数。具4n2 − 2n + 41形式的质数则以蓝点标记。 欧拉指出函数 n 2 + n + 41 {\displaystyle n^{2}+n+41\,} 于 0 ≤ n < 40时会给出质数[33][34]，此一事实导致了艰深的代数数论，或更具体地说为黑格纳数。当n更大时，该函数会给出合数值。哈代- 李特伍德猜想（Hardy-Littlewood conjecture）能给出一个有关具整数系数a、b与c的二次多项式 f ( n ) = a x 2 + b x + c {\displaystyle f(n)=ax^{2}+bx+c\,} 的值为质数之机率的一个渐近预测，并能以对数积分Li(n)及系数a、b、c来表示。不过，该程式已被证实难以取得：仍未知是否存在一个二次多项式（a ≠ 0）能给出无限多个质数。乌岚螺旋将所有自然数以螺旋的方法描绘。令人惊讶的是，质数会群聚在某些对角线上，表示有些二次多项式会比其他二次多项式给出更多个质数值来。 未解决的问题[编辑] ζ函数与黎曼猜想[编辑] 主条目：黎曼猜想 ζ函数ζ(s)的图。在s=1时，该函数会有极点，亦即会趋近于无限大。 黎曼ζ函数ζ(s)被定义为一无穷级数 ζ ( s ) = ∑ n = 1 ∞ 1 n s , {\displaystyle \zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}},} 其中，s为实数部分大于1的一个复数。由算术基本定理可证得，该级数会等于下面的无穷乘积 ∏ p prime 1 1 − p − s {\displaystyle \prod _{p{\text{ prime}}}{\frac {1}{1-p^{-s}}}} 。 ζ函数与质数密切相关。例如，存在无限多个质数这个事实也可以使用ζ函数看出：若只有有限多个质数，则ζ(1)将会是个有限值。不过，调和级数1 + 1/2 + 1/3 + 1/4 + ...会发散，所以必须有无限多个质数。另一个能看见ζ函数的丰富性，并一瞥现代代数数论的例子为下面的恒等式（巴塞尔问题，由欧拉给出）： ζ ( 2 ) = ∏ p 1 1 − p − 2 = π 2 6 {\displaystyle \zeta (2)=\prod _{p}{\frac {1}{1-p^{-2}}}={\frac {\pi ^{2}}{6}}} 。 ζ(2)的倒数6/π2，是两个随机选定的数字会互质的机率[35][36]。 未被证明的“黎曼猜想”，于1859年提出，表示除s = −2, −4, ...,外，ζ函数所有的根，其实数部分均为1/2。此一猜想与质数间的关连在于，该猜想实际上是在说，质数在正整数中出现频率和统计学的随机不同；若假设为真，质数计算函数便可有效掌握，在大数时不再需要近似求值。从物理的观点来看，这大约是在说，质数分布的不规则性仅来自于随机的杂讯。从数学的观点来看，则大约是在说，质数的渐近分布（质数定理表示小于x的质数约有x/log x个）在x周围的区间内，于区间长度远小于x的平方根时亦成立。此一猜想一般认为是正确的。 其他猜想[编辑] 更多信息：分类:素数猜想 除了黎曼猜想之外，还有许多其他的猜想存在。虽然这些猜想的陈述大多很简单，但许多猜想经过了数十年仍提不出证明，如4个兰道问题，从1912年提出至今仍然未解。其中一个为哥德巴赫猜想，该猜想认为每个大于2的偶数n都可表示成两个质数之和。至于2011年2月，这个猜想对最大达n = 2 · 1017的所有数字都会成立[37]。较弱形式的哥德巴赫猜想已被证明，如维诺格拉多夫定理，该定理表示每个足够大的奇数都可表示成三个质数之和。陈氏定理表示，每个足够大的偶数都可表示成一个质数与一个半质数（两个质数的乘积）之和。此外，任一个偶数均可写成六个质数之和[38]。数论研究这些问题的分支称之为加法数论。反哥德巴赫猜想，所有的正偶数n都可以表示成两个质数之差，但此猜想可由波利尼亚克猜想类推证明。 其他猜想处理是否有无限多个具某些限制的质数这类问题。据猜想，存在无限多个费波那契质数[39]与无限多个梅森质数，但没有无限多个费马质数[40]。还不知道是否存在无限多个维费里希质数与欧几里得质数。 第三种类型的猜想涉及到质数的分布情形。据猜想，存在无限多对孪生质数，即有无限多对相差2的质数（孪生质数猜想）。波利尼亚克猜想（英语：Polignac's conjecture）是比孪生质数猜想更强的一个猜想，该猜想表示存在无限多对相差2n的连续质数[41]。据猜想，存在无限多个具n2 + 1形式的质数[42]。上述猜想都是申策尔猜想的特例。布罗卡猜想表示，在两个大于2的连续质数之平方数之间，总是会有至少4个质数。勒让德猜想表示，对每个正整数n，n2与(n + 1)2间总会存在一个质数。克拉梅尔猜想可导出勒让德猜想。 应用[编辑] 长期以来，数论，尤其是对质数的研究，一般都会被认为是典型的纯数学，除了求知的趣味之外，没有其他应用。特别是，一些数论学家，如英国数学家戈弗雷·哈罗德·哈代即对其工作绝对不会有任何在军事上的重大性感到自豪[43]。然而，此一观点在1970年代时遭到粉碎，当质数被公开宣布可以作为产生公钥加密演算法的基础之时。质数现在也被用在杂凑表与伪乱数产生器（英语：Pseudo-random number generator）里。 旋转机被设计成在每个转片上有不同数目的销，在每个转片上的销的数量都会是质数，亦或是会与其他转片上的销的数量互质。这有助于在重复所有的组合之前，让所有转片的可能组合都能出现过一次。[来源请求] 国际标准书号的最后一码为校验码，其演算法使用到了11是个质数的这个事实[来源请求]。 在汽车变速箱齿轮的设计上，相邻的两个大小齿轮齿数最好设计成素数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强耐用度减少故障。 在害虫的生物生长周期与杀虫剂使用之间的关系上，杀虫剂的素数次数的使用也得到了证明。实验表明，素数次数地使用杀虫剂是最合理的：都是使用在害虫繁殖的高潮期，而且害虫很难产生抗药性[来源请求]。 以素数形式无规律变化的导弹和鱼雷可以使敌人不易拦截[来源请求]。 模一质数与有限体之运算[编辑] 主条目：模运算 “模运算”使用下列数字修改了一般的运算 { 0 , 1 , 2 , … , n − 1 } , {\displaystyle \{0,1,2,\dots ,n-1\},\,} 其中n是个固定的自然数，称之为“模”。计算加法、减法及乘法都与一般的运算一样，不过负数或大于n − 1的数字出现时，会被除以n所得的馀数取代。例如，对n=7，3+5为1，而不是8，因为8除以7馀1。这通常念为“3+5同馀于1模7”，并标记为 3 + 5 ≡ 1 ( mod 7 ) {\displaystyle 3+5\equiv 1{\pmod {7}}} 。 同样地，6 + 1 ≡ 0 (mod 7)、2 - 5 ≡ 4 (mod 7)，因为 -3 + 7 = 4，以及3 · 4 ≡ 5 (mod 7)，因为12除以7馀5。加法与乘法在整数里常见的标准性质在模运算里也依然有效。使用抽象代数的说法，由上述整数所组成之集合，亦标记为Z/nZ，且因此为一可交换环。不过，除法在模运算里不一定都是可行的。例如，对n=6，方程 3 ⋅ x ≡ 2 ( mod 6 ) , {\displaystyle 3\cdot x\equiv 2{\pmod {6}},} 的解x会类比于2/3，无解，亦可透过计算3 · 0、...、3 · 5模6看出。不过，有关质数的不同性质如下：除法在模运算里是可行的，若且唯若n为质数。等价地说，n为质数，若且唯若所有满足2 ≤ m ≤ n − 1的整数m都会与n 互质，亦即其公因数只有1。实际上，对n=7，方程 3 ⋅ x ≡ 2 ( mod 7 ) , {\displaystyle 3\cdot x\equiv 2\ \ (\operatorname {mod} \ 7),} 会有唯一的解x = 3。因此，对任何质数p，Z/pZ（亦标记为Fp）也会是个体，或更具体地说，是个有限体，因为该集合包含有限多（即p）个元素。 许多定理可以透过从此一抽象的方式检查Fp而导出。例如，费马小定理表示 a p − 1 ≡ 1 ( mod p ) {\displaystyle a^{p-1}\equiv 1(\operatorname {mod} \ p)} ，其中a为任一不被p整除的整数。该定理即可使用这些概念证得。这意味著 ∑ a = 1 p − 1 a p − 1 ≡ ( p − 1 ) ⋅ 1 ≡ − 1 ( mod p ) {\displaystyle \sum _{a=1}^{p-1}a^{p-1}\equiv (p-1)\cdot 1\equiv -1{\pmod {p}}} 。 吾乡-朱加猜想表示，上述公式亦是p为质数的必要条件。另一个费马小定理的推论如下：若p为2与5之外的其他质数，1/p总是个循环小数，其周期为p − 1或p − 1的因数。分数1/p依q（10以外的整数）为基底表示亦有类似的效果，只要p不是q的质因数的话。威尔逊定理表示，整数p > 1为质数，若且唯若阶乘 (p − 1)! + 1可被p整除。此外，整数n > 4为合数，若且唯若 (n − 1)!可被n整除。 其他数学里出现的质数[编辑] 许多数学领域里会大量使用到质数。举有限群的理论为例，西罗定理即是一例。该定理表示，若G是个有限群，且pn为质数p可整除G的阶的最大幂次，则G会有个pn阶的子群。此外，任意质数阶的群均为循环群（拉格朗日定理）。 公开金钥加密[编辑] 主条目：公开金钥加密 几个公开金钥加密演算法，如RSA与迪菲－赫尔曼金钥交换，都是以大质数为其基础（如512位元的质数常被用于RSA里，而1024位元的质数则一般被迪菲-赫尔曼金钥交换所采用）。RSA依靠计算出两个（大）质数的相乘会比找出相乘后的数的两个质因数容易出许多这个假设。迪菲－赫尔曼金钥交换依靠存在模幂次的有效演算法，但相反运算的离散对数仍被认为是个困难的问题此一事实。 自然里的质数[编辑] 周期蝉属里的蝉在其演化策略上使用到质数[44]。蝉会在地底下以幼虫的形态度过其一生中的大部分时间。周期蝉只会在7年、13年或17年后化蛹，然后从洞穴里出现、飞行、交配、产卵，并在至多数周后死亡。此一演化策略的原因据信是因为若出现的周期为质数年，掠食者就很难演化成以周期蝉为主食的动物[45]。若周期蝉出现的周期为非质数年，如12年，则每2年、3年、4年、6年或12年出现一次的掠食者就一定遇得到周期蝉。经过200年以后，假设14年与15年出现一次的周期蝉，其掠食者的平均数量，会比13年与17年出现一次的周期蝉，高出2%[46]。虽然相差不大，此一优势似乎已足够驱动天择，选择具质数年生命周期的这些昆虫。 据猜测，ζ函数的根与复数量子系统的能阶有关[47]。 推广[编辑] 质数的概念是如此的重要，以致此一概念被以不同方式推广至数学的不同领域里去。通常，“质”（prime）可在适当的意义下，用来表示具有最小性或不可分解性。例如，质体是指一个包含0与1的体F的最小子体。质体必为有理数或具有p个元素的有限体，这也是其名称的缘由[48]。若任一物件基本上均可唯一地分解成较小的部分，则这些较小的部分也会用“质”这个字来形容。例如，在纽结理论里，质纽结是指不可分解的纽结，亦即该纽结不可写成两个非平凡纽结的连通和。任一纽结均可唯一地表示为质纽约的连通和[49]。质模型与三维质流形亦为此类型的例子。 环内的素元[编辑] 主条目：素元和不可约元素 质数应用于任一可交换环R（具加法、减法与乘法的代数结构）的元素，可产生两个更为一般的概念：“素元”与“不可约元素”。R的元素称为素元，若该元素不为0或单位元素，且给定R内的元素x与y，若p可除以xy，则p可除以x或y。一元素称为不可约元素，若该元素不为单位元素，且无法写成两个不是单位元素之环元素的乘积。在整数环Z里，由素元所组成的集合等于由不可约元素所组成的集合，为 { … , − 11 , − 7 , − 5 , − 3 , − 2 , 2 , 3 , 5 , 7 , 11 , … } {\displaystyle \{\dots ,-11,-7,-5,-3,-2,2,3,5,7,11,\dots \}\,} 。 在任一环R里，每个素元都是不可约元素。反之不一定成立，但在唯一分解整环里会成立。 算术基本定理在唯一分解整环里仍然成立。此类整环的一个例子为高斯整数Z[i]，由具a + bi（其中a与b为任意整数）形式的复数所组成之集合。其素元称之为“高斯质数”。不是所有的质数都是高斯质数：在这个较大的环Z[i]之中，2可被分解成两个高斯质数 (1 + i)与 (1 - i)之乘积。有理质数（即在有理数里的素元），具4k+3形式者为高斯素数；具4k+1形式者则不是。 质理想[编辑] 主条目：质理想 在环论里，数的概念一般被理想所取代。“质理想”广义化了质元素的概念，为由质元素产生的主理想，是在交换代数、代数数论与代数几何里的重要工具与研究对象。整数环的质理想为理想 (0)、(2)、(3)、(5)、(7)、(11)、…算术基本定理被广义化成准素分解，可将每个在可交换诺特环里的理想表示成准素理想（为质数幂次的一适合广义化）的交集[50]。 透过环的谱这个概念，质理想成为代数几何物件的点[51]。算术几何也受益于这个概念，且许多概念会同时存在于几何与数论之内。例如，对一扩张体的质理想分解（这是代数数论里的一个基本问题），与几何里的分歧具有某些相似之处。此类分歧问题甚至在只关注整数的数论问题里也会出现。例如，二次体的整数环内的质理想可被用来证明二次互反律。二次互反律讨论下面二次方程 x 2 ≡ p ( mod q ) , {\displaystyle x^{2}\equiv p\ \ ({\text{mod }}q),\,} 是否有整数解，其中x为整数，p与q为（一般）质数[52]。早期对费马最后定理证明之尝试，于恩斯特·库默尔引入正则素数后达到了高潮。正则质数是指无法在由下列式子（其中a0、…、ap−1为整数，ζ则是能使ζp = 1的复数） a 0 + a 1 ζ + ⋯ + a p − 1 ζ p − 1 , {\displaystyle a_{0}+a_{1}\zeta +\cdots +a_{p-1}\zeta ^{p-1}\,,} 组成的环里，使得唯一分解定理失效的质数[53]。 赋值[编辑] 赋值理论研究由一个体K映射至实数R的某个函数（称之为赋值）[54]。每个此类赋值都能给出一个 K上的拓扑，且两个赋值被称为等价，若两者有相同拓扑。K的质数为一赋值的等价类。例如，一个有理数q的p进赋值被定义为整数vp(q)，使得 q = p v p ( q ) r s , {\displaystyle q=p^{v_{p}(q)}{\frac {r}{s}},} 其中r与s不被p所整除。例如，v3(18/7) = 2。p进范数被定义为[nb 1] | q | p := p − v p ( q ) . {\displaystyle \left|q\right|_{p}:=p^{-v_{p}(q)}.\,} 特别的是，当一个数字乘上p时，其范数会变小，与一般的绝对赋值（亦称为无限质数）形成明显的对比。当透过绝对赋值完备有理数会得出由实数所组成的体，透过p进范数完备有理数则会得出由p进数所组成的体[55]。实际上，依据奥斯特洛夫斯基定理，上述两种方法是完备有理数的所有方法。一些与有理数或更一般化之大域体有关的算术问题，可能可以被转换至完备（或局部）体上。此一局部-全域原则再次地强调了质数对于数论的重要性。 在艺术与文学里[编辑] 质数也影响了许多的艺术家与作家。法国作曲家奥立佛·梅湘使用质数创造出无节拍音乐。在《La Nativite du Seigneur》与《Quatre etudes de rythme》等作品里，梅湘同时采用由不同质数给定之长度的基调，创造出不可预测的节奏：第三个练习曲《Neumes rythmiques》中出现了质数41、43、47及53。据梅湘所述，此类作曲方式是“由自然的运动，自由且不均匀的持续运动中获得的灵感”[56]。 NASA科学家卡尔·萨根在他的科幻小说《接触未来》（Contact）里，认为质数可作为与外星人沟通的一种方式。这种想法是他与美国天文学家法兰克·德雷克于1975年闲聊时形成的[57]。 许多电影，如《异次元杀阵》（Cube）、《神鬼尖兵》（Sneakers）、《越爱越美丽》（The Mirror Has Two Faces）及《美丽境界》（A Beautiful Mind），均反映出大众对质数与密码学之神秘的迷恋[58]。保罗·裘唐诺所著的小说《质数的孤独》（The Solitude of Prime Numbers）里，质数被用来比喻寂寞与孤独，被描述成整数之间的“局外人”[来源请求]。 荒木飞吕彦所创作的日本漫画《JoJo的奇妙冒险》第六部《石之海》的反派普奇神父喜欢数质数，他认为质数是孤独的数字，并透过数质数安抚他紧张的情绪。 另见[编辑] 阿德曼-波门伦斯-鲁梅利质数测试 Bonse不等式 布朗筛法 伯恩赛德定理 契博塔耶夫密度定理 中国馀数定理 卡伦数 非法质数 质数列表 梅森质数 可乘数论 普通数域筛选法 贝潘测试 实际数 质k元组 自由黎曼气体 二次剩馀问题 RSA数 光滑数 超质数 胡道尔数 幸运素数 素数判定法则 埃拉托斯特尼筛法 孪生素数 三胞胎素数 PrimeGrid GIMPS 质数大富豪 注记[编辑] ^ Some sources also put | q | p := e − v p ( q ) . {\displaystyle \left|q\right|_{p}:=e^{-v_{p}(q)}.\,} . ^ GIMPS Project Discovers Largest Known Prime Number: 274,207,281-1. 互联网梅森素数大搜索计划. （原始内容存档于2019-04-07）. ^ Dudley, Underwood, Elementary number theory 2nd, W. H. Freeman and Co., 1978, ISBN 978-0-7167-0076-0 , p. 10, section 2 ^ Dudley 1978, Section 2, Theorem 2 ^ Dudley 1978, Section 2, Lemma 5 ^ 如见David E. Joyce对几何原本的注记，Book VII, definitions 1 and 2 （页面存档备份，存于互联网档案馆） ^ 6.0 6.1 存档副本. [2015-08-23]. （原始内容存档于2015-04-19）. ^ Weisstein, Eric W., "Goldbach Conjecture," MathWorld ^ Riesel 1994, p. 36 ^ Conway & Guy 1996, pp. 129–130 ^ Derbyshire, John, The Prime Number Theorem, Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics, Washington, D.C.: Joseph Henry Press: 33, 2003, ISBN 978-0-309-08549-6, OCLC 249210614 使用|accessdate=需要含有|url= (帮助) ^ ""Arguments for and against the primality of 1 （页面存档备份，存于互联网档案馆）". ^ "Why is the number one not prime?". [2015-08-23]. （原始内容存档于2008-05-09）. ^ The Largest Known Prime by Year: A Brief History （页面存档备份，存于互联网档案馆） Prime Curios!: 17014…05727 (39-digits) （页面存档备份，存于互联网档案馆） ^ 例如，Beiler写道，数论学家恩斯特·库默尔热爱他的理想数，该数与质数密切相关，“因为这些数没有被任何实际应用所玷污”。Katz则写道，爱德蒙·兰道（他最为人所知的是对质数分布的相关研究）“厌恶数学的实际应用”，且因为这个理由，规避几何等已知有所用途之学科。Beiler, Albert H., Recreations in the Theory of Numbers: The Queen of Mathematics Entertains, Dover: 2, 1966 [2015-08-23], ISBN 9780486210964, （原始内容存档于2021-04-17） . Katz, Shaul, Berlin roots—Zionist incarnation: the ethos of pure mathematics and the beginnings of the Einstein Institute of Mathematics at the Hebrew University of Jerusalem, Science in Context, 2004, 17 (1-2): 199–234, MR 2089305, doi:10.1017/S0269889704000092 ^ Letter （页面存档备份，存于互联网档案馆） in Latin from Goldbach to Euler, July 1730. ^ Furstenberg 1955 ^ Ribenboim 2004, p. 4 ^ James Williamson (translator and commentator), The Elements of Euclid, With Dissertations, Clarendon Press, Oxford, 1782, page 63, English translation of Euclid's proof （页面存档备份，存于互联网档案馆） ^ Hardy, Michael; Woodgold, Catherine. Prime Simplicity. Mathematical Intelligencer. 2009, 31 (4): 44–52. doi:10.1007/s00283-009-9064-8. ^ Apostol, Tom M., Introduction to Analytic Number Theory, Berlin, New York: Springer-Verlag, 1976, ISBN 978-0-387-90163-3 , Section 1.6, Theorem 1.13 ^ Apostol 1976, Section 4.8, Theorem 4.12 ^ （Lehmer 1909）. ^ Record 12-Million-Digit Prime Number Nets $100,000 Prize. Electronic Frontier Foundation. 2009-10-14 [2010-01-04]. （原始内容存档于2021-01-20）. ^ EFF Cooperative Computing Awards. Electronic Frontier Foundation. [2010-01-04]. （原始内容存档于2010-04-02）. ^ Chris K. Caldwell. The Top Twenty: Factorial. Primes.utm.edu. [2013-02-05]. （原始内容存档于2013-04-10）. ^ Chris K. Caldwell. The Top Twenty: Primorial. Primes.utm.edu. [2013-02-05]. （原始内容存档于2021-05-06）. ^ Chris K. Caldwell. The Top Twenty: Twin Primes. Primes.utm.edu. [2013-02-05]. （原始内容存档于2013-01-27）. ^ Havil 2003, p. 171 ^ Serge Tabachnikov. Kvant Selecta Algebra and Analysis. American Mathematical Society. 1999-01-01: 13– [2015-08-25]. ISBN 978-0-8218-1915-9. （原始内容存档于2021-04-17）. ^ Matiyasevich, Yuri V., Formulas for Prime Numbers, Tabachnikov, Serge (编), Kvant Selecta: Algebra and Analysis, II, American Mathematical Society: 13–24, 1999 [2015-08-23], ISBN 978-0-8218-1915-9, （原始内容存档于2021-04-17） ^ （Tom M. Apostol 1976）, Section 4.6, Theorem 4.7 ^ （Ben Green & Terence Tao 2008） ^ Hua 2009，第176-177页. ^ Wolfram, Stephen. "evaluate x^2−x+41 for x from 0..40". from Wolfram Alpha: Computational Knowledge Engine, Wolfram Research. [2021-05-18]. （原始内容存档于2020-03-21） （英语）. ^ Caldwell, Chris. What is the probability that gcd(n,m)=1?. The Prime Pages. [2013-09-06]. （原始内容存档于2021-04-21）. ^ C. S. Ogilvy & J. T. Anderson Excursions in Number Theory, pp. 29–35, Dover Publications Inc., 1988 ISBN 978-0-486-25778-5 ^ Tomás Oliveira e Silva. Goldbach conjecture verification. Ieeta.pt. 2011-04-09 [2011-05-21]. （原始内容存档于2013-04-21）. ^ Ramaré, O., On šnirel'man's constant, Annali della Scuola Normale Superiore di Pisa. Classe di Scienze. Serie IV, 1995, 22 (4): 645–706 [2008-08-22], （原始内容存档于2020-09-19）. ^ Caldwell, Chris, The Top Twenty: Lucas Number （页面存档备份，存于互联网档案馆） at The Prime Pages. ^ E.g., see Guy 1981, problem A3, pp. 7–8 ^ Tattersall, J.J., Elementary number theory in nine chapters, Cambridge University Press, 2005 [2015-08-23], ISBN 978-0-521-85014-8, （原始内容存档于2020-03-21） , p. 112 ^ Weisstein, Eric W. (编). Landau's Problems. at MathWorld--A Wolfram Web Resource. Wolfram Research, Inc. （英语）. ^ Hardy 1940 "No one has yet discovered any warlike purpose to be served by the theory of numbers or relativity, and it seems unlikely that anyone will do so for many years." ^ Goles, E.; Schulz, O.; Markus, M. Prime number selection of cycles in a predator-prey model. Complexity. 2001, 6 (4): 33–38. doi:10.1002/cplx.1040. ^ Paulo R. A. Campos, Viviane M. de Oliveira, Ronaldo Giro, and Douglas S. Galvão., Emergence of Prime Numbers as the Result of Evolutionary Strategy, Physical Review Letters, 2004, 93 (9): 098107, Bibcode:2004PhRvL..93i8107C, arXiv:q-bio/0406017 , doi:10.1103/PhysRevLett.93.098107. 使用|accessdate=需要含有|url= (帮助) ^ Invasion of the Brood. The Economist. 2004-05-06 [2006-11-26]. （原始内容存档于2009-01-25）. ^ Ivars Peterson. The Return of Zeta. MAA Online. 1999-06-28 [2008-03-14]. （原始内容存档于2007-10-20）. ^ Lang, Serge, Algebra, Graduate Texts in Mathematics 211, Berlin, New York: Springer-Verlag, 2002, ISBN 978-0-387-95385-4, MR 1878556 , Section II.1, p. 90 ^ Schubert, H. "Die eindeutige Zerlegbarkeit eines Knotens in Primknoten". S.-B Heidelberger Akad. Wiss. Math.-Nat. Kl. 1949 (1949), 57–104. ^ Eisenbud 1995, section 3.3. ^ Shafarevich, Basic Algebraic Geometry volume 2 (Schemes and Complex Manifolds), p. 5, section V.1 ^ Neukirch, Algebraic Number theory, p. 50, Section I.8 ^ Neukirch, Algebraic Number theory, p. 38, Section I.7 ^ Endler, Valuation Theory, p. 1 ^ Gouvea: p-adic numbers: an introduction, Chapter 3, p. 43 ^ Hill 1995. ^ Carl Pomerance. Prime Numbers and the Search for Extraterrestrial Intelligence (PDF). [2007-12-22]. （原始内容存档 (PDF)于2021-05-06）. ^ The music of primes. [2015-08-23]. （原始内容存档于2015-10-09）. 参考资料[编辑] Apostol, Thomas M., Introduction to Analytic Number Theory, New York: Springer, 1976, ISBN 0-387-90163-9 Conway, John Horton; Guy, Richard K., The Book of Numbers, New York: Copernicus, 1996, ISBN 978-0-387-97993-9 Crandall, Richard; Pomerance, Carl, Prime Numbers: A Computational Perspective 2nd, Berlin, New York: Springer-Verlag, 2005, ISBN 978-0-387-25282-7 Derbyshire, John, Prime obsession, Joseph Henry Press, Washington, DC, 2003, ISBN 978-0-309-08549-6, MR 1968857 Eisenbud, David, Commutative algebra, Graduate Texts in Mathematics 150, Berlin, New York: Springer-Verlag, 1995, ISBN 978-0-387-94268-1, MR 1322960 Fraleigh, John B., A First Course In Abstract Algebra 2nd, Reading: Addison-Wesley, 1976, ISBN 0-201-01984-1 Furstenberg, Harry, On the infinitude of primes, The American Mathematical Monthly (Mathematical Association of America), 1955, 62 (5): 353, JSTOR 2307043, doi:10.2307/2307043 Green, Ben; Tao, Terence, The primes contain arbitrarily long arithmetic progressions, Annals of Mathematics, 2008, 167 (2): 481–547, arXiv:math.NT/0404188 , doi:10.4007/annals.2008.167.481 Gowers, Timothy, Mathematics: A Very Short Introduction, Oxford University Press, 2002, ISBN 978-0-19-285361-5 Guy, Richard K., Unsolved Problems in Number Theory, Berlin, New York: Springer-Verlag, 1981, ISBN 978-0-387-90593-8 Havil, Julian, Gamma: Exploring Euler's Constant, Princeton University Press, 2003, ISBN 978-0-691-09983-5 Hardy, Godfrey Harold, A Course of Pure Mathematics, Cambridge University Press, 1908, ISBN 978-0-521-09227-2 Hardy, Godfrey Harold, A Mathematician's Apology, Cambridge University Press, 1940, ISBN 978-0-521-42706-7 Herstein, I. N., Topics In Algebra, Waltham: Blaisdell Publishing Company, 1964, ISBN 978-1114541016 Hill, Peter Jensen (编), The Messiaen companion, Portland, Or: Amadeus Press, 1995, ISBN 978-0-931340-95-6 Hua, L.K., Additive Theory of Prime Numbers, Translations of Mathematical Monographs 13, Providence, RI: American Mathematical Society: 176–177, 2009 [1965], ISBN 978-0821849422, MR 0194404, OCLC 824812353 Lehmer, D. H., Factor table for the first ten millions containing the smallest factor of every number not divisible by 2, 3, 5, or 7 between the limits 0 and 10017000, Washington, D.C.: Carnegie Institution of Washington, 1909 McCoy, Neal H., Introduction To Modern Algebra, Revised Edition, Boston: Allyn and Bacon, 1968, LCCN 68-15225 Narkiewicz, Wladyslaw, The development of prime number theory: from Euclid to Hardy and Littlewood, Springer Monographs in Mathematics, Berlin, New York: Springer-Verlag, 2000, ISBN 978-3-540-66289-1 Ribenboim, Paulo, The little book of bigger primes, Berlin, New York: Springer-Verlag, 2004, ISBN 978-0-387-20169-6 Riesel, Hans, Prime numbers and computer methods for factorization, Basel, Switzerland: Birkhäuser, 1994, ISBN 978-0-8176-3743-9 Sabbagh, Karl, The Riemann hypothesis, Farrar, Straus and Giroux, New York, 2003, ISBN 978-0-374-25007-2, MR 1979664 du Sautoy, Marcus, The music of the primes, HarperCollins Publishers, 2003 [2015-08-23], ISBN 978-0-06-621070-4, MR 2060134, （原始内容存档于2015-09-07） 外部链接[编辑] 查看维基词典中的词条“质数”。 维基教科书中的相关电子教程：小学数学/质数与合数 Hazewinkel, Michiel (编), Prime number, 数学百科全书, Springer, 2001, ISBN 978-1-55608-010-4 Caldwell, Chris, The Prime Pages at primes.utm.edu（页面存档备份，存于互联网档案馆）. Prime Numbers，In Our Time (BBC Radio 4)（英语：BBC Radio 4）的《In Our Time》节目。 An Introduction to Analytic Number Theory, by Ilan Vardi and Cyril Banderier（页面存档备份，存于互联网档案馆） Plus teacher and student package: prime numbers（页面存档备份，存于互联网档案馆） from Plus, the free online mathematics magazine produced by the Millennium Mathematics Project at the University of Cambridge. 出现质数实验 （页面存档备份，存于互联网档案馆） 出现可以被整除的机率 质数产生器与计算器[编辑] Prime Number Checker （页面存档备份，存于互联网档案馆） identifies the smallest prime factor of a number. Fast Online primality test with factorization（页面存档备份，存于互联网档案馆） makes use of the Elliptic Curve Method (up to thousand-digits numbers, requires Java). Huge database of prime numbers（页面存档备份，存于互联网档案馆） Prime Numbers up to 1 trillion （页面存档备份，存于互联网档案馆） 素数发生器和校验器 （页面存档备份，存于互联网档案馆） 查论编和因数有关的整数分类简介 质因数分解 因数 元因数 除数函数 质因数 算术基本定理 依因数分解分类 质数 合数 半素数 普洛尼克数 楔形数 无平方数因数的数 幂数 质数幂 平方数 立方数 次方数 阿喀琉斯数 光滑数 正规数 粗糙数 不寻常数 依因数和分类 完全数 殆完全数 准完全数 多重完全数 Hemiperfect数 Hyperperfect number（英语：Hyperperfect number） 超完全数 元完全数 半完全数 本原半完全数 实际数 有许多因数 过剩数 本原过剩数 高过剩数 超过剩数 可罗萨里过剩数 高合成数 Superior highly composite number（英语：Superior highly composite number） 奇异数 和真因子和数列有关 不可及数 相亲数 交际数 婚约数 其他 亏数 友谊数 孤独数 卓越数 欧尔调和数 佩服数 节俭数 等数位数 奢侈数 规范控制 BNF: cb11932592t (data) FAST: 1041241 GND: 4047263-2 J9U: 987007538747905171 LCCN: sh85093218 LNB: 000232578 NDL: 00571462 NKC: ph139050 取自“https://zh.wikipedia.org/w/index.php?title=质数&oldid=80711832” 分类：素数整数数列隐藏分类：含有访问日期但无网址的引用的页面CS1英语来源 (en)使用ISBN魔术链接的页面含有英语的条目自2022年7月有未列明来源语句的条目有未列明来源语句的条目包含BNF标识符的维基百科条目包含FAST标识符的维基百科条目包含GND标识符的维基百科条目包含J9U标识符的维基百科条目包含LCCN标识符的维基百科条目包含LNB标识符的维基百科条目包含NDL标识符的维基百科条目包含NKC标识符的维基百科条目 本页面最后修订于2024年1月29日 (星期一) 16:57。 本站的全部文字在知识共享 署名-相同方式共享 4.0协议之条款下提供，附加条款亦可能应用。（请参阅使用条款） Wikipedia®和维基百科标志是维基媒体基金会的注册商标；维基™是维基媒体基金会的商标。 维基媒体基金会是按美国国内税收法501(c)(3)登记的非营利慈善机构。 隐私政策 关于维基百科 免责声明 行为准则 开发者 统计 Cookie声明 手机版视图 开关有限宽度模式 数论（一）质数 - 知乎切换模式写文章登录/注册数论（一）质数小螺蛎数量这一概念应该是人类能够最原始而直接地从生活中感受到的数学内容之一了。想一想我们最早接触到的数学应该就是认识数字了吧。在对自然数的研究中有一个很重要的概念，就是质数以及与其相对应的合数，这一回我们就来聊一聊质数。质因数分解在研究一个正整数时，最直接的一种方法就是将其分解(factorization)。但在分解的过程中有不同的方法，如12既可以写成2×6，也可以写成3×4。那么有没有一种方法将其分解为唯一的形式呢？答案就是继续分解，直到无法分解为止。根据算数基本定理（Fundamental Theorem of Arithmetic）,所有大于1的自然数都可以被完全分解成质数的乘积的形式。如上面的例子，12=2×6=2×2×3；或写成12=3×4=3×2×2；我们发现这两种分解方法都得到了同样的结果。这样无法再分解的数就是质数，或称素数。而那种可以继续分解的数就是合数。这是一个比较直观的定义。准确地说，质数是除去1和它自身之外，再没有其他因数的正整数。因为1的存在，任何正整数都可以写成1乘以其自身。说到这里，想必读者对质数已有了一个直观的了解。就像我们刚刚所说的，质数的定义就是想要描述那些基本的数。质数之于合数，打个不甚恰当的比方，就好比字母相对于单词。质数作为基本的单位，可以合成各种合数；而任何合数都是由质数合成而来的。质数的英文prime number中的prime就有首要的、基本的意思。但不知为何，在汉语中prime number写成了质数。可能是prime也有优质的意思吧。只能说是中文单字命名时的一种缺陷了。而合数(composite number)就更能顾名思义了，composite即为合成的意思。质数的特征不同于英文中的字母只有有限个这一特点，质数有无限多个。这一发现早在早在公元前就被欧几里得(Euclid)提出：假设质数的个数只有有限个：2，3，5，7…p，p为最大的质数。则所有的正整数都由这些质数合成而来，也就是所有的数都可以被2，3，5，7…p中的某些数整除，那么，2×3×5×7×…×p+1这个合数肯定也能够被2，3，5，7...p中的某些数整除。但是，从2×3×5×7×…×p+1这个表达式我们就能看出来，它并不能被2，3，5，7...p中的任何数整除，也就形成了悖论，所以我们之前的假设并不成立，也就说明了一定有无限多个质数。（反证法的典型应用）质数都有哪些呢？刚才我们提到的2，3，5，7都是质数，我们可以按照质数的定义继续寻找，2，3，5，7，11，13，17，19，23...质数与质数之间看似毫无关系，但仔细观察还是能找出一些规律的。下图中列出了100以内的质数。根据算术基本定理，所有合数都能够写成质数乘积的形式，因此100以内的合数必然是2，3，5或7中的至少一个数的倍数，这是因为若非如此，则这个合数必然是大于7的质数之积，则超出了100这一范围。这也就是说，在100以内的数中，合数必为2或3或5或7的倍数。除此之外的数则为质数（习惯上规定1既不是质数也不是合数）。因为2的倍数以2、4、6、8、0结尾，5的倍数以5、0结尾，所以大于10的质数必然不第2列、第4列、第5列、第6列、第8列和第10列。其余列中在除掉3的倍数和7的倍数，剩余的则为质数。关于如何快速判断出倍数关系的问题会在以后讨论。发布于 2020-06-19 09:03数学数论赞同 104 条评论分享喜欢收藏申请 质数 - MBA智库百科 全球专业中文经管百科，由121,994位网友共同编写而成，共计435,717个条目 查看 条目讨论编辑 收藏 简体中文繁体中文 工具箱▼ 链入页面 链出更改 上传文件 特殊页面 可打印版 永久链接 质数 用手机看条目 扫一扫，手机看条目 出自 MBA智库百科(https://wiki.mbalib.com/) 质数(prime number) 目录 1 什么是质数 2 质数的个数 3 质数的性质 4 质数的相关定理 5 质数的应用 [编辑] 什么是质数 质数又称素数，有无限个。一个大于1的自然数，除了1和它本身外，不能被其他自然数(质数)整除，换句话说就是该数除了1和它本身以外不再有其他的因数；否则称为合数。 根据算术基本定理，每一个比1大的整数，要么本身是一个质数，要么可以写成一系列质数的乘积；而且如果不考虑这些质数在乘积中的顺序，那么写出来的形式是唯一的。最小的质数是2。 目前为止，人们未找到一个公式可求出所有质数。 [编辑] 质数的个数 质数的个数是无穷的。欧几里得的《几何原本》中有一个经典的证明。它使用了证明常用的方法：反证法。具体证明如下：假设质数只有有限的n个，从小到大依次排列为p1，p2，……，pn，设N=p1×p2×……×pn，那么，N+1是素数或者不是素数。 如果N+1为素数，则N+1要大于p1，p2，……，pn，所以它不在那些假设的素数集合中。 如果N+1为合数，因为任何一个合数都可以分解为几个素数的积；而N和N+1的最大公约数是1，所以N+1不可能被p1，p2，……，pn整除，所以该合数分解得到的素因数肯定不在假设的素数集合中。 因此无论该数是素数还是合数，都意味着在假设的有限个素数之外还存在着其他素数。所以原先的假设不成立。也就是说，素数有无穷多个。 其他数学家给出了一些不同的证明。欧拉利用黎曼函数证明了全部素数的倒数之和是发散的，恩斯特·库默的证明更为简洁，HillelFurstenberg则用拓扑学加以证明。 [编辑] 质数的性质 质数具有许多独特的性质： (1)质数p的约数只有两个：1和p。 (2)初等数学基本定理：任一大于1的自然数，要么本身是质数，要么可以分解为几个质数之积，且这种分解是唯一的。 (3)质数的个数是无限的。 (4)质数的个数公式π(n) 是不减函数。 (5)若n为正整数,在n2到(n + 1)2之间至少有一个质数。 (6)若n为大于或等于2的正整数，在n到n!之间至少有一个质数。 (7)若质数p为不超过n( )的最大质数，则 。 [编辑] 质数的相关定理 1.在一个大于1的数a和它的2倍之间(即区间(a, 2a]中)必存在至少一个素数。 2.存在任意长度的素数等差数列。(格林和陶哲轩，2004年[1] ) 3.一个偶数可以写成两个质数之和，其中每一个数字都最多只有9个质因数。(挪威数学家布朗，1920年) 4.一个偶数必定可以写成一个质数加上一个合成数，其中的因子个数有上界。(瑞尼，1948年) 5.一个偶数必定可以写成一个质数加上一个最多由5个因子所组成的合成数。后来，有人简称这结果为 (1 + 5) (中国潘承洞，1968年) 6.一个充分大偶数必定可以写成一个素数加上一个最多由2个质因子所组成的合成数。简称为 (1 + 2) (中国陈景润) [编辑] 质数的应用 质数被利用在密码学上，所谓的公钥就是将想要传递的信息在编码时加入质数，编码之后传送给收信人，任何人收到此信息后，若没有此收信人所拥有的密钥，则解密的过程中(实为寻找素数的过程)，将会因为找质数的过程(分解质因数)过久，使即使取得信息也会无意义。 在汽车变速箱齿轮的设计上，相邻的两个大小齿轮齿数最好设计成质数，以增加两齿轮内两个相同的齿相遇啮合次数的最小公倍数，可增强耐用度减少故障。 在害虫的生物生长周期与杀虫剂使用之间的关系上，杀虫剂的质数次数的使用也得到了证明。实验表明，质数次数地使用杀虫剂是最合理的：都是使用在害虫繁殖的高潮期，而且害虫很难产生抗药性。 以质数形式无规律变化的导弹和鱼雷可以使敌人不易拦截。 多数生物的生命周期也是质数(单位为年)，这样可以最大程度地减少碰见天敌的机会。 来自"https://wiki.mbalib.com/wiki/%E8%B4%A8%E6%95%B0" 打开MBA智库App, 阅读完整内容 打开App 本条目对我有帮助19 赏 MBA智库APP 扫一扫，下载MBA智库APP 分享到： 温馨提示 复制该内容请前往MBA智库App 立即前往App 如果您认为本条目还有待完善，需要补充新内容或修改错误内容，请编辑条目或投诉举报。 本条目相关文档 “质数与合数”教学设计与评析 5页 五年级：质数和合数学案 7页 五年级数学：质数和合数 9页 五年级数学：找质数 5页 五年级数学课题：找质数 6页 五年级数学：《质数和合数》教案 5页 五年级数学：质数和合数教案 5页 五年级数学：质数和合数练习 4页 五年级数学：《质数和合数》教学教案 7页 五年级数学：《找质数》教学实录 8页 更多相关文档 本条目相关课程 本条目由以下用户参与贡献 Mis铭. 页面分类: 统计术语 评论(共0条)提示:评论内容为网友针对条目"质数"展开的讨论，与本站观点立场无关。 发表评论请文明上网，理性发言并遵守有关规定。 首页 文档 百科 课堂 商学院 资讯 知识点 国际MBA 商城 企业服务 问答 首页
专题
管理 营销 经济 金融 人力资源 咨询 财务 品牌 证券 物流 贸易 商学院 法律 人物 分类索引 百科VIP 百科VIP会员权益 无广告阅读 免验证复制 开通/续费百科VIP 登录 消息 昵称未设置
百科VIP
未开通 收藏夹 账号安全中心 我的页面 我的贡献 我的讨论页 我的设置 退出登录 打开APP 导航 最新资讯 最新评论 最新推荐 热门推荐 编辑实验 使用帮助 创建条目 随便看看 本周推荐 最多推荐 翻异别勘智能卡食品新质生产力包装印刷生产线第一性原理宗庆后纪梵希头寸 奶头乐理论蘑菇管理定律猴子管理法则情绪ABC理论垃圾人定律100个最流行的管理词汇破窗效应INFPSWOT分析模型21天效应 以上内容根据网友推荐自动排序生成 下载APP
此页面最后修订：17:04,2015年7月14日. 智库首页 - 百科首页 - 关于百科 -
客户端 -
人才招聘 -
广告合作 - 权利通知 -
联系我们 -
免责声明 - 友情链接 ©2024 MBAlib.com, All rights reserved. 闽公网安备 35020302032707号 意见反馈 问题分类 类型 反馈内容 添加图片(选填)0/9 联系方式 取消 提交 提交成功 反馈结果请前往 MBA智库App 查看 （我的 > 帮助与反馈 > 我的反馈） 知道了 质数就是奇数？合数就是偶数？ - 知乎切换模式写文章登录/注册质数就是奇数？合数就是偶数？泫沌一个158的小学咸鱼老师要理解上面的两个问题，必须得先知道上面这四个数的概念。什么是偶数？整数内，能被2整除的数，叫偶数。例如8，8÷2=4，得到整数商4，所以8是偶数。什么是奇数？整数内，不能被2整除的叫奇数。例如7，7÷2=3……1，得到商3还有余数1，不能整除，所以7是奇数。什么是质数？只有1和它本身的数叫质数。例如2，2的因数只有两个:1和2，没有其他的因数，所以2是质数。什么是合数？有两个以上因数的数叫合数。例如35，35的因数有四个，分别是1.35.5.7，因数个数超过2个，所以35是合数。那质数就是奇数，合数就是偶数这句话说法对吗？当然是不对的，我们可以举一个反例，15不能被2整除，是奇数；但是它的因数有1.15.3.5这四个，所以15是合数。这个反例可以推翻第一个说法。再举一个反例，35有1.35.5.7四个因数，所以35是合数；将35÷2=17……1，无法整除，所以35是奇数。那么合数就是偶数这是错误的说法。反观这个问题，其实本身就存在一定的错误。奇数和偶数要看的是能不能被2整除，质数和合数要看这个数的因数个数。会产生这个错误主要是因为，对这四个数的概念不理解。所以我们在学习数学的时候，首先一定要对数学概念进行理解消化，才能将知识点灵魂的应用到题目里，这题数学才不会没头没脑，无从下手。在数学课堂上，主要要听的不只是老师的解题技巧，老师对概念的解释也要注意听，听老师怎么分析，重点在放在哪些字眼，哪些句子。比如上面偶数的概念“整数中，能够被2整除的数，叫做偶数。”这个概念重点放在“整数，被2整除”这几个字眼上。从概念我们可以明确两个方向:1.偶数是针对整数范围，小数就直接排除在外；2.偶数是能被2整除的，是2的倍数，不是2的倍数排除在外。学习数学有很多技巧，希望每个孩子都能在数学的海洋里，寻到一把自己的金钥匙。发布于 2020-02-18 18:53赞同 357 条评论分享喜欢收藏申请
质数 - 维基百科，自由的百科全书
数论（一）质数 - 知乎
合数（数字分类基础概念）_百度百科
字分类基础概念）_百度百科 网页新闻贴吧知道网盘图片视频地图文库资讯采购百科百度首页登录注册进入词条全站搜索帮助首页秒懂百科特色百科知识专题加入百科百科团队权威合作下载百科APP个人中心合数是一个多义词，请在下列义项上选择浏览（共2个义项）展开添加义项合数[hé shù]播报讨论上传视频数字分类基础概念收藏查看我的收藏0有用+10本词条由“科普中国”科学百科词条编写与应用工作项目 审核 。合数是指在大于1的整数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。与之相对的是质数，而1既不属于质数也不属于合数。最小的合数是4。其中，完全数与相亲数是以它为基础的。中文名合数外文名Composite number适用领域(威尔逊定理)应用学科数学性 质大于1且除1和这个数本身，还能被其他正整数整除的整数类 型数字分类基础概念所属范围自然数目录1定义2性质3类型4相关▪质数▪算术基本定理定义播报编辑合数指自然数中除了能被1和本身整除外，还能被其他数（0除外）整除的数。 [1]性质播报编辑所有大于2的偶数都是合数。所有大于5的奇数中，个位为5的都是合数。除0以外，所有个位为0的自然数都是合数。所有个位为4，6，8的自然数都是合数。最小的（偶）合数为4，最小的奇合数为9。每一个合数都可以以唯一形式被写成质数的乘积，即分解质因数。(算术基本定理)对任一大于5的合数(威尔逊定理):类型播报编辑合数的一种方法为计算其质因数的个数。一个有两个质因数的合数称为半质数，有三个质因数的合数则称为楔形数。在一些的应用中，亦可以将合数分为有奇数的质因数的合数及有偶数的质因数的合数。对于后者，（其中μ为默比乌斯函数且''x''为质因数个数的一半），而前者则为注意，对于质数，此函数会传回 -1，且。而对于有一个或多个重复质因数的数字''n''，。另一种分类合数的方法为计算其因数的个数。所有的合数都至少有三个因数。一质数的平方数，其因数有。一数若有著比它小的整数都还多的因数，则称此数为高合成数。另外，完全平方数的因数个数为奇数个，而其他的合数则皆为偶数个。相关播报编辑质数只有1和它本身两个因数的自然数，叫质数（或称素数）。（如：由2÷1=2，2÷2=1，可知2的因数只有1和它本身2这两个因数，所以2就是质数。与之相对立的是合数：“除了1和它本身两个因数外，还有其它因数的数，叫合数。”如：4÷1=4，4÷2=2，4÷4=1，很显然，4的因数除了1和它本身4这两个因数以外，还有因数2，所以4是合数。）100以内的质数有2、3、5、7、11、13、17、19、23、29、31、37、41、43、47、53、59、61、67、71、73、79、83、89、97，一共有25个。质数的个数是无穷的。欧几里得的《几何原本》中的证明使用了证明常用的方法：反证法。具体证明如下：假设质数只有有限的n个，从小到大依次排列为p1，p2，……，pn，设N=p1×p2×……×pn，那么，N+1是素数或者不是素数。如果N+1为素数，则N+1要大于p1，p2，……，pn，所以它不在那些假设的素数集合中。如果N+1为合数，因为任何一个合数都可以分解为几个素数的积；而N和N+1的最大公约数是1，所以N+1不可能被p1，p2，……，pn整除，所以该合数分解得到的素因数肯定不在假设的素数集合中。因此无论该数是素数还是合数，都意味着在假设的有限个素数之外还存在着其他素数。所以原先的假设不成立。也就是说，素数有无穷多个。其他数学家给出了一些不同的证明。欧拉利用黎曼函数证明了全部素数的倒数之和是发散的，恩斯特·库默的证明更为简洁，Hillel Furstenberg则用拓扑学加以证明。任何一个大于1的自然数N，都可以唯一分解成有限个质数的乘积，这里P1质数就是奇数？合数就是偶数？ - 知乎