质数

質しつ數すう，又また称たたえ素数そすう，指ゆび在ざい大だい於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$，使用しよう此方こちら法ほう者しゃ需逐一いち測はか試ためし2與あずか${\sqrt {n}}$之これ間あいだ的てき質しつ數すう，確保かくほ它們無む一能いちのう整除せいじょ$n$。對たい於較大だい或ある一いち些具特別とくべつ形式けいしき（如梅森もり數すう）的てき自然しぜん數すう，人にん們通常つうじょう使用しよう較有效率こうりつ的てき演算えんざん法ほう測はか試ためし其是否ひ為ため質しつ數すう（例れい如2^82589933-1是ぜ直ちょく至いたり2024年ねん4月がつ為ため止どめ已やめ知ち最大さいだい的てき梅森うめもり質ただし數すう，也是直ちょく至いたり2024年ねん4月がつ為ため止どめ已やめ知ち最大さいだい的てき質しつ數すう）。雖然人じん們仍未み發現はつげん可か以完全ぜん區別くべつ質しつ數すう與あずか合ごう數すう的てき公式こうしき，甚至研究けんきゅう質しつ數すう分布ぶんぷ時じ相當そうとう有力ゆうりょく的てき篩ふるい法ほう也會碰到奇偶きぐう性せい問題もんだい（也就是ぜ多種たしゅ篩ふるい法ほう都と無法むほう區別くべつ質しつ數すう跟兩個りゃんこ質しつ數すう相乘そうじょう的てき合ごう數すう的てき問題もんだい），但ただし已やめ建けん構了質しつ數すう的てき分ぶん佈模式しき（亦また即そく質しつ數すう在ざい大數たいすう時どき的てき統計とうけい模も式しき）。19世紀せいき晚期ばんき得え到いた證明しょうめい的てき質しつ數すう定理ていり指出さしで：一いち個こ任意にんい自然しぜん數すうn為ため質しつ數すう的てき機き率りつ反はん比ひ於其數すう位い（或ある$n$的てき对数）。

許多きょた有ゆう關せき質しつ數すう的てき問題もんだい依然いぜん未み解かい，如哥德巴ともえ赫猜想そう（每まい個こ大だい於2的てき偶數ぐうすう可か表示ひょうじ成なり兩個りゃんこ素數そすう之の和わ）及孿生質しつ數すう猜想（存在そんざい無窮むきゅう多た對たい相差おうさつ2的てき質しつ數すう）。這些問題もんだい促進そくしん了りょう數すう論ろん各個かっこ分ぶん支ささえ的てき發展はってん，主要しゅよう在ざい於數字すうじ的てき解析かいせき或ある代數だいすう方面ほうめん。質しつ數すう被ひ用よう於資訊科技わざ裡うら的てき幾いく個こ程ほど序じょ中ちゅう，如公おおやけ鑰加密みつ利用りよう了りょう難なん以將大數たいすう分解ぶんかい成なり其質因數いんすう之の類るい的てき性質せいしつ。質しつ數すう亦また在ざい其他數學すうがく領域りょういき裡うら形成けいせい了りょう各種かくしゅ廣義こうぎ化か的てき質しつ數すう概念がいねん，主要しゅよう出で現在げんざい代数だいすう裡うら，如質しつ元素げんそ及質しつ理想りそう。

定義ていぎ和わ例れい子こ

一いち個こ自然しぜん數すう（如1、2、3、4、5、6等とう）若わか恰有兩個りゃんこ正ただし因數いんすう（1及此數すう本身ほんみ），則のり稱しょう之の為ため質しつ數すう。大だい於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$均ひとし至いたり少しょう有ゆう三さん個こ不同ふどう的てき因數いんすう，即そく1、2與あずか$n$。這意指ゆび$n$不ふ是ぜ質しつ數すう。因よし此，「奇き質しつ數すう」係がかり指ゆび任にん何なん大だい於2的てき質しつ數すう。類似るいじ地ち，當とう使用しよう一般いっぱん的てき十じゅう進しん位い制せい時じ，所有しょゆう大だい於5的てき質しつ數すう，其尾數すう均ひとし為ため1、3、7或ある9，因いん為ため尾お數すう0、2、4、6、8為ため2的てき倍數ばいすう，尾び數すう為ため0或ある5的てき數字すうじ為ため5的てき倍數ばいすう。

若わか$n$為ため一いち自然しぜん數すう，則のり1與あずか$n$會かい整除せいじょ$n$。因よし此，質しつ數すう的てき條件じょうけん可か重じゅう新しん敘述為ため：一いち個こ數字すうじ為ため質しつ數すう，若わか該數大だい於1，且沒有ゆう

$2,3,\ldots ,n-1$

會かい整除せいじょ$n$。另一いち種しゅ敘述方式ほうしき為ため：一いち數すう$n>1$為ため質しつ數すう，若わか不能ふのう寫うつし成なり兩個りゃんこ整數せいすう$a$與あずか$b$的てき乘じょう積せき，其中這兩數すう均ひとし大だい於1：

$n=a\cdot b$.

換かわ句く話はなし說せつ，$n$為ため質しつ數すう，若わか$n$無法むほう分ぶん成なり數量すうりょう都と大だい於1且都相しょう同どう的てき各組かくくみ。

由よし所有しょゆう質しつ數すう組成そせい之の集合しゅうごう通常つうじょう標記ひょうき為ためP或ある$\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的てき整數せいすう均ひとし可か寫うつし成なり一個以上的質數之乘積，且除了りょう質しつ因數いんすう的てき排はい序じょ不同ふどう外がい是ぜ唯一ゆいいつ的てき。質しつ數すう可か被ひ認みとめ為ため是ぜ自然しぜん數すう的てき「基本きほん建材けんざい」，例れい如：

23244	= 2 · 2 · 3 · 13 · 149
	= 22 · 3 · 13 · 149. （22表示ひょうじ2的てき平方へいほう或ある2次じ方かた。）

如同此例一般いっぱん，相そう同どう的てき因數いんすう可能かのう出現しゅつげん多た次つぎ。一いち個こ數すうn的てき分解ぶんかい：

$n=p_{1}\cdot p_{2}\cdot \ldots \cdot p_{t}$

成なり（有限ゆうげん多た個こ）質しつ因數いんすう$p_{1}$、$p_{2}$、……、$p_{t}$，稱しょう之の為ため$n$的てき「因數いんすう分解ぶんかい」。算術さんじゅつ基本きほん定理ていり可か以重新しん敘述為ため，任にん一質數分解除了因數的排序外，都と是ぜ唯一ゆいいつ的てき。因よし此，儘管實務じつむ上じょう存在そんざい許多きょた質しつ數すう分解ぶんかい演算えんざん法ほう來らい分解ぶんかい較大的てき數字すうじ，但ただし最後さいご都と會得えとく到いた相あい同どう的てき結果けっか。

若わか$p$為ため質しつ數すう，且$p$可か整除せいじょ整數せいすう的てき乘じょう積せき$ab$，則のり$p$可か整除せいじょ$a$或ある可か整除せいじょ$b$。此一命題被稱為歐幾里得引理，被ひ用もちい來らい證明しょうめい質しつ數すう分解ぶんかい的てき唯ただ一いち性せい。

1是ぜ否ひ為ため質しつ數すう

最さい早期そうき的てき希まれ臘人甚至不ふ將しょう1視し為ため是ぜ一いち個こ數字すうじ，因いん此不會かい認みとめ為ため1是ぜ質しつ數すう。到いた了りょう中ちゅう世紀せいき與あずか文藝ぶんげい復興ふっこう時期じき，許多きょた數學すうがく家か將はた1納入のうにゅう作為さくい第だい一いち個こ質しつ數すう。到いた18世紀せいき中期ちゅうき，克かつ里さと斯蒂安やす·哥德巴ともえ赫在ざい他た與あずか李り昂のぼる哈德·歐おう拉ひしげ著名ちょめい的てき通信つうしん裡うら將しょう1列れつ為ため第だい一いち個こ質しつ數すう，但ただし歐おう拉ひしげ不ふ同意どうい。然しか而，到いた了りょう19世紀せいき，仍有許多きょた數學すうがく家か認みとめ為ため數字すうじ1是これ個こ質しつ數すう。例れい如，德とく里さと克かつ·諾だく曼·雷かみなり默だま（Derrick Norman Lehmer）在ざい他た那な最大さいだい達たち10,006,721的てき質しつ數列すうれつ表ひょう中なか，將はた1列れつ為ため第だい1個いっこ質しつ數すう。昂のぼる利り·勒貝格かく據よりどころ說せつ是ぜ最後さいご一いち個こ稱たたえ1為ため質しつ數すう的てき職業しょくぎょう數學すうがく家か。到いた了りょう20世紀せいき初はつ，數學すうがく家か開始かいし認みとめ為ため1不ふ是ぜ個こ質しつ數すう，但ただし反はん而作為さくい「單位たんい」此一特殊とくしゅ類別るいべつ。

許多きょた數學すうがく成果せいか在ざい稱しょう1為ため質しつ數すう時じ，仍將有效ゆうこう，但ただし歐おう幾里いくさと何なん的てき算術さんじゅつ基本きほん定理ていり（如上じょじょう所しょ述じゅつ）則のり無法むほう不ふ重じゅう新しん敘述而仍然しか成立せいりつ。例れい如，數字すうじ15可か分解ぶんかい成なり3 · 5及 1 · 3 · 5；若わか1被ひ允許いんきょ為ため一いち個こ質しつ數すう，則のり這兩個りゃんこ表示法ひょうじほう將しょう會かい被ひ認みとめ為ため是ぜ將しょう15分解ぶんかい至いたり質しつ數すう的てき不同ふどう方法ほうほう，使つかい得とく此一定理ていり的てき陳述ちんじゅつ必須ひっす被ひ修正しゅうせい。同樣どうよう地ち，若わか將しょう1視し為ため質しつ數すう，埃ほこり拉ひしげ托たく斯特尼あま篩ふるい法ほう將はた無法むほう正常せいじょう運うん作さく：若わか將しょう1視し為ため質しつ數すう，此一篩法將會排除掉所有1的てき倍數ばいすう（即そく所有しょゆう其他的てき數すう），只ただ留とめ下か數字すうじ1。此外，質しつ數すう有ゆう幾いく個こ1所しょ沒ぼつ有ゆう的てき性質せいしつ，如歐拉ひしげ函數かんすう的てき對應たいおう值，以及除數じょすう函數かんすう的てき總和そうわ。

歷史れきし

埃ほこり拉ひしげ托たく斯特尼あま篩ふるい法ほう是これ個こ找出在ざい一特定整數以下的所有質數之簡單演算えんざん法ほう，由ゆかり古希こき臘數學すうがく家か埃ほこり拉ひしげ托たく斯特尼あま於公元もと前まえ3世紀せいき發明はつめい。

在ざい古こ埃及えじぷと人的じんてき倖存紀き錄ろく中ちゅう，有ゆう跡あと象ぞう顯示けんじ他た們對質たいしつ數すう已やめ有ゆう部分ぶぶん認識にんしき：例れい如，在ざい萊因德とく數學すうがく紙し草書そうしょ中なか的てき古こ埃及えじぷと分數ぶんすう展開てんかい時じ，對質たいしつ數すう與あずか對たい合ごう數すう有ゆう著ちょ完全かんぜん不同ふどう的てき類型るいけい。不ふ過か，對質たいしつ數すう有ゆう過か具體ぐたい研究けんきゅう的てき最早もはや倖存紀き錄ろく來らい自じ古希こき臘。公おおやけ元もと前まえ300年ねん左右さゆう的てき《幾何きか原本げんぽん》包含ほうがん與あずか質しつ數すう有ゆう關せき的てき重要じゅうよう定理ていり，如有無限むげん多た個こ質しつ數すう，以及算術さんじゅつ基本きほん定理ていり。歐おう幾里いくさと得とく亦また展示てんじ如何いか從したがえ梅森うめもり質ただし數すう建けん構出完全かんぜん數すう。埃ほこり拉ひしげ托たく斯特尼あま提出ていしゅつ的てき埃ほこり拉ひしげ托たく斯特尼あま篩ふるい法ほう是ぜ用よう來らい計算けいさん質しつ數すう的てき一いち個こ簡單かんたん方法ほうほう，雖然今こん天てん使用しよう電腦でんのう發現はつげん的てき大だい質しつ數すう無法むほう使用しよう這個方法ほうほう找出。

希まれ臘之後ご，到いた17世紀せいき之の前まえ，質しつ數すう的てき研究けんきゅう少しょう有ゆう進展しんてん。1640年ねん，皮かわ埃ほこり爾なんじ·德とく·費ひ馬ば敘述了りょう費ひ馬ば小しょう定理ていり（之これ後ご才ざい被ひ萊布尼あま茨いばら與あずか歐おう拉ひしげ證明しょうめい）。費ひ馬ば亦また推測すいそく，所有しょゆう具ぐ$2^{2^{n}}+1$形式けいしき的てき數すう均ひとし為ため質しつ數すう（稱しょう之の為ため費ひ馬うま數すう），並なみ驗けん證しょう至いたり$n=4$（即そく2¹⁶ + 1）不ふ過か，後ご來由らいゆ歐おう拉ひしげ發現はつげん，下した一いち個こ費ひ馬ば數すう2³² + 1即そく為ため合ごう數すう，且實際ぎわ上じょう其他已やめ知的ちてき費ひ馬ば數すう都と不ふ是ぜ質しつ數すう。法ほう國こく修道しゅうどう士し馬うま蘭らん·梅森うめもり發現はつげん有ゆう的てき質しつ數すう具ぐ$2^{p}-1$的てき形式けいしき，其中$p$為ため質しつ數すう。為ため紀き念ねん他た的てき貢獻こうけん，此類質しつ數すう後來こうらい被ひ稱しょう為ため梅森うめもり質ただし數すう。

歐おう拉ひしげ在ざい數すう論ろん中ちゅう的てき成果せいか，許多きょた與あずか質しつ數すう有ゆう關せき。他た證明しょうめい無窮むきゅう級數きゅうすう${\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+{\frac {1}{11}}+\ldots$會かい發散はっさん。1747年ねん，歐おう拉ひしげ證明しょうめい每ごと個こ偶完全かんぜん數すう都と確實かくじつ為ため$2^{p-1}(2^{p}-1)$的てき形式けいしき，其中第だい二個因數為梅森質數。

19世紀せいき初はつ，勒壤得とく與あずか高こう斯獨立どくりつ推測すいそく，當とう$x$趨向すうこう無限むげん大だい時じ，小しょう於$x$的てき質しつ數すう數量すうりょう會かい趨近於${\frac {x}{\ln x}}$，其中$\ln x$為ため$x$的てき自然しぜん對數たいすう。黎はじむ曼於1859年ねん有ゆう關せきζぜーた函數かんすう的てき論文ろんぶん中ちゅう勾勒出で一いち個こ程ほど式しき，導出どうしゅつ了りょう質しつ數すう定理ていり的てき證明しょうめい。其大綱たいこう由ゆかり雅まさ克かつ·阿達あだち馬うま與あずか夏なつ尔-让·德とく拉ひしげ瓦かわら莱·普ふ桑くわ所ところ完成かんせい，他た們於1896年ねん獨立どくりつ證明しょうめい出で質しつ數すう定理ていり。

證明しょうめい一個大數是否為質數通常無法由試除法來達成。許多きょた數學すうがく家か已やめ研究けんきゅう過大かだい數すう的てき質しつ數すう測はか試ためし，通常つうじょう侷限於特定とくてい的てき數字すうじ形式けいしき。其中包括ほうかつ費ひ馬ば數すう的てき貝かい潘はん測はか試ためし（1877年ねん）、普羅ふら絲いと定理ていり（約やく1878年ねん）、盧の卡斯-萊默質しつ數すう判定はんてい法ほう（1856年ねん起おこり）及廣義こうぎ盧の卡斯質しつ數すう測はか試ためし。較近期き的てき演算えんざん法ほう，如APRT-CL、ECPP及AKS等ひとし，均ひとし可か作用さよう於任意にんい數字すうじ上じょう，但ただし仍慢上じょう許多きょた。

長期ちょうき以來いらい，質しつ數すう被ひ認みとめ為ため在ざい純じゅん數學すうがく以外いがい的てき地方ちほう只ただ有ゆう極少きょくしょう數すう的てき應用おうよう。到いた了りょう1970年代ねんだい，發明はつめい公共こうきょう密みつ鑰加密みつ這個概念がいねん之これ後ご，情況じょうきょう改變かいへん了りょう，質しつ數すう變成へんせい了りょうRSA加か密みつ演算えんざん法ほう等とう一いち階かい演算えんざん法ほう之の基礎きそ。

自じ1951年ねん以來いらい，所有しょゆう已やめ知ち最大さいだい的てき質しつ數すう都みやこ由ゆかり電腦でんのう所ところ發現はつげん。對たい更さら大だい質しつ數すう的てき搜さがせ尋ひろ已やめ在ざい數すう學界がっかい以外いがい的てき地方ちほう產さん生出おいで興趣きょうしゅ。網あみ際ぎわ網もう路ろ梅森うめもり質ただし數すう大だい搜索そうさく及其他用たよう來らい尋ひろ找大質しつ數すう的てき分散ぶんさん式しき運算うんざん計畫けいかく變へん得とく流行りゅうこう，在ざい數學すうがく家か仍持續じぞく與あずか質しつ數すう理論りろん奮鬥的てき同時どうじ。

素数そすう的てき数すう目もく

主しゅ条目じょうもく：歐おう幾里いくさと得とく定理ていり

存在そんざい無限むげん多おお個こ質しつ數すう。另一いち種しゅ說法せっぽう為ため，質しつ數すう序列じょれつ

2, 3, 5, 7, 11, 13, ...

永遠えいえん不ふ會かい結束けっそく。此一陳述ちんじゅつ被ひ稱しょう為ため「歐おう幾里いくさと得とく定理ていり」，以古希こき臘數しわす學がく家か歐おう幾里いくさと得とく為ため名めい，因いん為ため他た提出ていしゅつ了りょう該陳述ちんじゅつ的てき第だい一いち個こ證明しょうめい。已やめ知ち存在そんざい其他更さら多た的てき證明しょうめい，包括ほうかつ歐おう拉ひしげ的てき分析ぶんせき證明しょうめい、哥德巴ともえ赫依據いきょ費ひ馬うま數すう的てき證明しょうめい、弗どる斯滕伯はく格かく使用しよう一般いっぱん拓ひらけ撲なぐ學がく的てき證明しょうめい，以及庫くら默だま爾しか優雅ゆうが的てき證明しょうめい。

歐おう幾里いくさと得とく的てき證明しょうめい

歐おう幾里いくさと得とく的てき證明しょうめい取と任にん一個由質數所組成的有限集合$S$。該證明しょうめい的てき關せき鍵かぎ想そう法ほう為ため考慮こうりょ$S$內所有しょゆう質しつ數すう相乘そうじょう後ご加か一いち的てき一いち個こ數字すうじ：

$N=1+\prod _{p\in S}p$。

如同其他自然しぜん數すう一般いっぱん，$N$可か被ひ至いたり少しょう一いち個こ質しつ數すう整除せいじょ（即そく使つかいN本身ほんみ為ため質しつ數すう亦また同どう）。

任にん何なん可か整除せいじょN的てき質しつ數すう都と不可能ふかのう是ぜ有限ゆうげん集合しゅうごう$S$內的元素げんそ（質しつ數すう），因いん為ため後者こうしゃ除じょN都會とかい餘あまり1。所以ゆえん，$N$可か被ひ其他質しつ數すう所しょ整除せいじょ。因よし此，任にん一個由質數所組成的有限集合，都と可か以擴展てん為ため更さら大だい個こ由よし質しつ數すう所しょ組成そせい之の集合しゅうごう。

這個證明しょうめい通常つうじょう會かい被ひ錯誤さくご地ち描述為ため，歐おう幾里いくさと得とく一開始假定一個包含所有質數的集合，並なみ導しるべ致矛盾むじゅん；或ある者もの是ぜ，該集合しゅうごう恰好かっこう包含ほうがんn個こ最小さいしょう的てき質しつ數すう，而不任意にんい個こ由よし質しつ數すう所しょ組成そせい之の集合しゅうごう。今日きょう，$n$個こ最小さいしょう質しつ數すう相乘そうじょう後ご加か一いち的てき一いち個こ數字すうじ，被ひ稱しょう為ため第だい$n$個こ歐おう幾里いくさと得とく數すう。

歐おう拉ひしげ的てき解析かいせき證明しょうめい

歐おう拉ひしげ的てき證明しょうめい使用しよう到いた質しつ數すう倒たおせ數すう的てき總和そうわ

$S(p)={\frac {1}{2}}+{\frac {1}{3}}+{\frac {1}{5}}+{\frac {1}{7}}+\cdots +{\frac {1}{p}}$。

當とう$p$夠大時じ，該和會かい大だい於任意にんい實數じっすう。這可證明しょうめい，存在そんざい無限むげん多た個こ質しつ數すう，否いや則のり該和將はた只ただ會かい增長ぞうちょう至いたり達たち到いた最大さいだい質しつ數すう$p$為ため止どめ。$S(p)$的てき增加ぞうか率りつ可か使用しよう梅うめ滕斯第だい二に定理ていり來らい量りょう化か。比較ひかく總和そうわ

${\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$趨向すうこう無限むげん大だい時じ，此和不ふ會かい變成へんせい無限むげん大だい（見み巴ともえ塞ふさが爾しか問題もんだい）。這意味あじ著ちょ，質しつ數すう比ひ自然しぜん數すう的てき平方へいほう更さら常つね出現しゅつげん。布ぬの朗ろう定理ていり指出さしで，孿生質しつ數すう倒たおせ數すう的てき總和そうわ

$\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$是ぜ否ひ為ため質しつ數すう有ゆう許多きょた種しゅ方法ほうほう。最さい基本きほん的てき程ほど序じょ為ため試ためし除法じょほう，但ただし因よし為ため速そく率りつ很慢，沒ぼつ有ゆう什麼いんも實際じっさい用よう處しょ。有ゆう一類現代的質數測試可適用於任意數字之上，另有一類更有效率的測試方法，則のり只ただ能のう適用てきよう於特定とくてい的てき數字すうじ之の上うえ。大だい多數たすう此類方法ほうほう只ただ能辨のうべん別べつ$n$是ぜ否ひ為ため質しつ數すう。也能給きゅう出で$n$的てき一いち個こ（或ある全部ぜんぶ）質しつ因數いんすう之の程ほど序じょ稱しょう之の為ため因數いんすう分解ぶんかい演算えんざん法ほう。

試ためし除法じょほう

主しゅ条目じょうもく：試ためし除法じょほう

測はか試ためし$n$是ぜ否ひ為ため質しつ數すう的てき最さい基本きほん方法ほうほう為ため試ためし除法じょほう。此一程ほど序じょ將はたn除じょ以每個こ大だい於1且小於等於$n$的てき平方根へいほうこん之これ整數せいすう$m$。若わか存在そんざい一個相除為整數的結果，則のり$n$不ふ是ぜ質しつ數すう；反はん之これ則そく是これ個こ質しつ數すう。實際じっさい上じょう，若わか$n=ab$是これ個こ合ごう數すう（其中$a$與あずか$b\neq 1$），則のり其中一いち個こ因數いんすう$a$或ある$b$必定ひつじょう至大しだい為ため${\sqrt {n}}$。例れい如，對たい$n=37$使用しよう試ためし除法じょほう，將はた37除じょ以$m=2,3,4,5,6$，沒ぼつ有ゆう一いち個こ數すう能のう整除せいじょ37，因いん此37為ため質しつ數すう。此一程序若能知道直至${\sqrt {n}}$的てき所有しょゆう質しつ數列すうれつ表ひょう，則のり可か以只檢けん查$m$為ため質しつ數すう的てき狀況じょうきょう，以提升ます效率こうりつ。例れい如，為ため檢けん查37是ぜ否ひ為ため質しつ數すう，只ただ有ゆう3個こ相しょう除じょ是ぜ必要ひつよう的てき（$m=2,3,5$），因いん為ため4與あずか6為ため合ごう數すう。

作為さくい一いち個こ簡單かんたん的てき方法ほうほう，試ためし除法じょほう在ざい測はか試ためし大だい整數せいすう時じ很快地ち會かい變へん得え不ふ切實せつじつ際ぎわ，因いん為ため可能かのう的てき因數いんすう數量すうりょう會かい隨ずい著ちょn的てき增加ぞうか而迅速そく增加ぞうか。依據いきょ下か文ぶん所しょ述じゅつ之の質しつ數すう定理ていり，小しょう於${\sqrt {n}}$的てき質しつ數すう之の數量すうりょう約やく為ため${\frac {\sqrt {n}}{\ln {\sqrt {n}}}}$，因いん此使用しよう試ためし除法じょほう測はか試ためし$n$是ぜ否ひ為ため質しつ數すう時じ，大約たいやく會かい需要じゅよう用よう到いた這麼多た的てき數字すうじ。對たい$n=10^{20}$，此一數すう值約為ため4.5億おく，對たい許多きょた實際じっさい應用おうよう而言都みやこ太ふとし過か龐大。

篩ふるい法ほう

一個能給出某個數值以下的所有質數之演算法，稱しょう之の為ため質しつ數すう篩ふるい法ほう，可用かよう於只使用しよう質しつ數すう的てき試ためし除法じょほう內。最さい古老ころう的てき一いち個こ例れい子こ為ため埃ほこり拉ひしげ托たく斯特尼あま篩ふるい法ほう（見上みかみ文あや），至いたり今こん仍最常つね被ひ使用しよう。阿おもね特金とっきん篩ふるい法ほう為ため另外一いち例れい。在ざい電腦でんのう出現しゅつげん之の前まえ，篩ふるい法ほう曾被用よう來らい給きゅう出で10⁷以下いか的てき質しつ數列すうれつ表ひょう。

質しつ數すう測はか試こころみ與あずか質しつ數すう證明しょうめい

主しゅ条目じょうもく：素性すじょう測はか試ためし

現代げんだい測はか試ためし一般いっぱん的てき數字すうじ$n$是ぜ否ひ為ため質しつ數すう的てき方法ほうほう可分かぶん成なり兩個りゃんこ主要しゅよう類型るいけい，隨ずい機き（或ある「蒙こうむ特とく卡洛」）與あずか確定かくてい性せい演算えんざん法ほう。確定かくてい性せい演算えんざん法ほう可か肯定こうてい辨別べんべつ一個數字是否為質數。例れい如，試ためし除法じょほう即そく是ぜ個こ確定かくてい性せい演算えんざん法ほう，因いん為ため若わか正確せいかく執行しっこう，該方法ほう總そう是ぜ可か以辨別べつ一個質數為質數，一いち個こ合ごう數すう為ため合ごう數すう。隨ずい機き演算えんざん法ほう一般いっぱん比較ひかく快かい，但ただし無法むほう完全かんぜん證明しょうめい一個數是否為質數。這類測はか試こころみ依よ靠もたれ部分ぶぶん隨ずい機き的てき方法ほうほう來らい測はか試ためし一いち個こ給きゅう定じょう的てき數字すうじ。例れい如，一測試在應用於質數時總是會通過，但ただし在ざい應用おうよう於合數すう時じ通過つうか的てき機き率りつ為ため$p$。若わか重じゅう復ふく這個測はか試ためし$n$次つぎ，且每次じ都と通過つうか，則のり該數為ため合あい數すう的てき機き率りつ為ため${\frac {1}{(1-p)^{n}}}$，會かい隨ずい著ちょ測はか試ためし次數じすう呈てい指數しすう下か滑すべり，因いん此可越來ごえく越えつ確信かくしん（雖然總そう是ぜ無法むほう完全かんぜん確信かくしん）該數為ため質しつ數すう。另一方面ほうめん，若わか測はか試ためし曾失敗しっぱい過か，則のり可知かち該數為ため合ごう數すう。

隨ずい機き測はか試ためし的てき一個特別簡單的例子為費ひ馬ば質しつ數すう判定はんてい法ほう，使用しよう到いた對たい任にん何なん整數せいすう$a$，$n^{p}\equiv n(\mod p)$，其中$p$為ため質しつ數すう的てき這個事實じじつ（費ひ馬ば小しょう定理ていり）。若わか想そう要よう測はか試ためし一いち個こ數字すうじ$b$是ぜ否ひ為ため質しつ數すう，則のり可か隨ずい機き選擇せんたく$n$來らい計算けいさん$n^{b}(\mod b)$的てき值。這個測はか試ためし的てき缺かけ點在てんざい於，有ゆう些合數すう（卡邁克かつ爾なんじ數すう）即そく使つかい不ふ是ぜ質しつ數すう，也會符合ふごう費ひ馬ば恆等こうとう式しき，因いん此這個こ測はか試ためし無法むほう辨別べんべつ質しつ數すう與あずか卡邁克かつ爾なんじ數すう，最小さいしょう的てき三個卡邁克爾數為561，1105，1729。卡邁克かつ爾なんじ數すう比ひ質しつ數すう還かえ少しょう上うえ許多きょた，所以ゆえん這個測はか試ためし在ざい實際じっさい應用おうよう上じょう還かえ是ぜ有用ゆうよう的てき。費ひ馬ば質しつ數すう判定はんてい法ほう更さら強大きょうだい的てき延伸えんしん方法ほうほう，包括ほうかつ貝かい利り-PSW、米べい勒-拉ひしげ賓まろうど與あずかSolovay-Strassen質しつ數すう測はか試ためし，都と保證ほしょう至いたり少しょう在ざい應用おうよう於合數すう時じ，有ゆう部分ぶぶん時候じこう會かい失敗しっぱい。

確定かくてい性せい演算えんざん法ほう不ふ會かい將はた合ごう數すう錯誤さくご判定はんてい為ため質しつ數すう。在ざい實務じつむ上じょう，最さい快かい的てき此類方法ほうほう為ため橢圓だえん曲線きょくせん質しつ數すう證明しょうめい。其運算うんざん時間じかん是ぜ透過とうか實務じつむ分析ぶんせき出來でき的てき，不ふ像ぞう最新さいしん的てきAKS質しつ數すう測はか試ためし，有ゆう已やめ被かむ嚴格げんかく證明しょうめい出來でき的てき複雜ふくざつ度ど。確定かくてい性せい演算えんざん法ほう通常つうじょう較隨機き演算えんざん法ほう來らい得とく慢，所以ゆえん一般會先使用隨機演算法，再さい採用さいよう較費時じ的てき確定かくてい性せい演算えんざん法ほう。

下面かめん表ひょう格かく列れつ出で一些質數測試。運算うんざん時間じかん以被測はか試ためし的てき數字すうじ$n$來らい表示ひょうじ，並なみ對たい隨ずい機き演算えんざん法ほう，以$k$表示ひょうじ其測試ためし次數じすう。此外，$\varepsilon$是ぜ指ゆび一いち任意にんい小しょう的てき正數せいすう，$\log$是ぜ指ゆび一いち無む特定とくてい基數きすう的てき對數たいすう。大だいO符號ふごう表示ひょうじ，像ぞう是ぜ在ざい橢圓だえん曲線きょくせん質しつ數すう證明しょうめい裡うら，所しょ需之運算うんざん時間じかん最長さいちょう為ため一いち常數じょうすう（與あずかn無關むせき，但ただし會かい與あずかεいぷしろん有ゆう關せき）乘じょう於log^{5+εいぷしろん}(n)。

測はか試ためし	發明はつめい於	類型るいけい	運算うんざん時間じかん	註記ちゅうき
AKS質しつ數すう測はか試ためし	2002	確定かくてい性せい	$O(\log ^{6+\varepsilon }(n))$
橢圓だえん曲線きょくせん質しつ數すう證明しょうめい	1977	確定かくてい性せい	$O(\log ^{5+\varepsilon }(n))$「實務じつむ分析ぶんせき」
貝かい利り-PSW質しつ數すう測はか試ためし	1980	隨ずい機き	$O(\log ^{3}n)$	無む已やめ知ち反例はんれい
米べい勒-拉ひしげ賓まろうど質しつ數すう判定はんてい法ほう	1980	隨ずい機き	$O(k\cdot \log ^{2+\varepsilon }(n))$	錯誤さくご機き率りつ$4^{-k}$
Solovay-Strassen質しつ數すう	1977	隨ずい機き	$O(k\cdot \log ^{3}n)$	錯誤さくご機き率りつ$2^{-k}$
費ひ馬ば質しつ數すう判定はんてい法ほう		隨ずい機き	$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為ため質しつ數すう）、質しつ數すう階かい乘じょう質しつ數すう、費ひ馬ば質しつ數すう與あずか梅森うめもり質ただし數すう（具ぐ2^p − 1形式けいしき的てき質しつ數すう，其中p為ため質しつ數すう）。盧の卡斯-雷かみなり默だま質しつ數すう測はか試ためし對たい這類形式けいしき的てき數すう特別とくべつ地ち快かい。這也是ぜ為ため何なん自じ電腦でんのう出現しゅつげん以來いらい，最大さいだい已やめ知ち質しつ數すう總會そうかい是ぜ梅森うめもり質ただし數すう的てき原因げんいん。

費ひ馬ば質しつ數すう具ぐ下か列れつ形式けいしき

F_k = 2^2k + 1,

其中，k為ため任意にんい自然しぜん數すう。費ひ馬ば質しつ數すう以皮かわ埃ほこり爾なんじ·德とく·費ひ馬ば為ため名めい，他た猜想此類數字すうじF_k均ひとし為ため質しつ數すう。費ひ馬ば認みとめ為ためF_k均ひとし為ため質しつ數すう的てき理由りゆう為ため此串列れつ的てき前まえ5個こ數字すうじ（3、5、17、257及65537）為ため質しつ數すう。不ふ過か，F₅卻為合ごう數すう，且直至いたり2015年ねん發現はつげん的てき其他費ひ馬ば數字すうじ也全都と是これ合ごう數すう。一いち個こ正ただしn邊あたり形がた可用かよう尺せき規ただし作圖さくず，若わか且唯若わか

n = 2ⁱ · m

其中，m為ため任意にんい個こ不同ふどう費ひ馬ば質しつ數すう之これ乘じょう積せき，及i為ため任にん一いち自然しぜん數すう，包括ほうかつ0。

下しも列れつ表ひょう格かく給きゅう出で各種かくしゅ形式けいしき的てき最大さいだい已やめ知ち質しつ數すう。有ゆう些質數すう使用しよう分散ぶんさん式しき計算けいさん找到。2009年ねん，網あみ際ぎわ網もう路ろ梅森うめもり質ただし數すう大だい搜索そうさく因いん為ため第だい一いち個こ發現はつげん具ぐ至いたり少しょう1,000萬まん個こ數すう位い的てき質しつ數すう，而獲得かくとく10萬美元的獎金。電子でんし前哨ぜんしょう基金ききん會かい亦また為ため具ぐ至いたり少しょう1億おく個こ數すう位い及10億個數位的質數分別提供15萬まん美び元もと及25萬美元的獎金。

類型るいけい	質しつ數すう	數すう位い	日にち期き	發現はつげん者しゃ
梅森うめもり質ただし數すう	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
質しつ數すう階かい乘じょう質しつ數すう	1098133# - 1	476,311	2012年ねん3月がつ	PrimeGrid
孿生質しつ數すうs	3756801695685×2666669 ± 1	200,700	2011年ねん12月	PrimeGrid

整數せいすう分解ぶんかい

主しゅ条目じょうもく：整數せいすう分解ぶんかい

給きゅう定じょう一いち合ごう數すうn，給きゅう出で一いち個こ（或ある全部ぜんぶ）質しつ因數いんすう的てき工作こうさく稱しょう之の為ためn的てき因數いんすう分解ぶんかい。橢圓だえん曲線きょくせん分解ぶんかい是ぜ一いち個こ依よ靠もたれ橢圓だえん曲線きょくせん上うえ的てき運算うんざん來らい分解ぶんかい質しつ因數いんすう的てき演算えんざん法ほう。

質しつ數すう分ふん佈

1975年ねん，數かず論ろん學がく家か唐から·察吉爾なんじ評論ひょうろん質しつ數すう

像ぞう生長せいちょう於自然しぜん數すう間あいだ的てき雜草ざっそう，似に乎不服從ふくじゅう機き率りつ之の外的がいてき法則ほうそく，（但ただし又また）表現ひょうげん出で驚おどろき人的じんてき規律きりつ性せい，並なみ有ゆう規範きはん其行為こうい之の法則ほうそく，且以軍事ぐんじ化か的てき精せい準じゅん度ど遵守じゅんしゅ著ちょ這些法則ほうそく。

大だい質しつ數すう的てき分ぶん佈，如在一給定數值以下有多少質數這個問題，可か由よし質しつ數すう定理ていり所しょ描述；但ただし有效ゆうこう描述第だいn個こ質しつ數すう的てき公式こうしき則のり仍未找到。

存在そんざい任意にんい長ちょう的てき連續れんぞく非ひ質しつ數すう數列すうれつ，如對每ごと個こ正せい整數せいすう$n$，從したがえ$(n+1)!+2$至いたり$(n+1)!+n+1$的てき$n$個こ連續れんぞく正せい整數せいすう都會とかい是ぜ合ごう數すう（因いん為ため若わか$k$為ため2至いたり$n+1$間あいだ的てき一いち整數せいすう，$(n+1)!+k$就可被ひk整除せいじょ）。

狄利克かつ雷かみなり定理ていり表示ひょうじ，取と兩個りゃんこ互質的てき整數せいすうa與あずかb，其線性せい多項式たこうしき

$p(n)=a+bn\,$

會かい有無うむ限げん多た個こ質しつ數すう值。該定理ていり亦また表示ひょうじ，這些質しつ數すう值的倒たおせ數すう和會かずえ發散はっさん，且具有ぐゆう相しょう同どうb的てき不同ふどう多項式たこうしき會かい有ゆう差さ不ふ多た相しょう同どう的てき質しつ數すう比例ひれい。

有ゆう關せき二次多項式的相關問題則尚無較好之理解。

質しつ數すう的てき公式こうしき

主しゅ条目じょうもく：質しつ數すう公式こうしき

對たい於質數すう，還かえ沒ぼっ有ゆう一いち個こ已やめ知的ちてき有效ゆうこう公式こうしき。例れい如，米べい爾なんじ斯定理ていり與あずか賴よりゆき特とく所ところ提ひさげ的てき一いち個こ定理ていり表示ひょうじ，存在そんざい實じつ常數じょうすうA>1與あずかμみゅー，使つかい得とく

$\left\lfloor A^{3^{n}}\right\rfloor {\text{ and }}\left\lfloor 2^{\dots ^{2^{2^{\mu }}}}\right\rfloor$

對たい任にん何なん自然しぜん數すうn而言，均ひとし為ため質しつ數すう。其中，$\lfloor -\rfloor$為ため高こう斯符號ごう，表示ひょうじ不ふ大だい於符號ごう內數字すうじ的てき最大さいだい整數せいすう。第だい二に個こ公式こうしき可か使用しよう伯はく特とく蘭らん-切きり比ひ雪夫ゆきお定理ていり得とく證しょう（由ゆかり切きり比ひ雪夫ゆきお第だい一いち個こ證しょう得とく）。該定理ていり表示ひょうじ，總そう是ぜ存在そんざい至いたり少しょう一いち個こ質しつ數すうp，使つかい得とく n < p < 2n − 2，其中n為ため大だい於3的てき任にん一いち自然しぜん數すう。第だい一いち個こ公式こうしき可か由ゆかり威い爾しか遜へりくだ定理ていり導出どうしゅつ，每まい個こ不同ふどう的てきn會かい對應たいおう到いた不同ふどう的てき質しつ數すう，除じょ了りょう數字すうじ2會かい有ゆう多た個こn對應たいおう到いた外そと。不ふ過か，這兩個りゃんこ公式こうしき都と需要じゅよう先さき計けい算出さんしゅつA或あるμみゅー的てき值來。

不ふ存在そんざい一個只會產生質數值的非常數多項式たこうしき，即そく使つかい該多項式たこうしき有ゆう許多きょた個こ變數へんすう。不ふ過か，存在そんざい具ぐ9個こ變數へんすう的てき丟番圖ず方かた程ほど，其參數すう具備ぐび以下いか性質せいしつ：該參數すう為ため質しつ數すう，若わか且唯若わか其方程ほど組ぐみ有ゆう自然しぜん數すう解かい。這可被ひ用もちい來らい獲得かくとく其所有しょゆう「正せい值」均ひとし為ため質しつ數すう的てき一いち個こ公式こうしき。

一特定數以下的質數之數量

主しゅ条目じょうもく：質しつ數すう定理ていり和わ質しつ數すう計算けいさん函數かんすう

圖ず中ちゅう的てき曲線きょくせん分別ふんべつ表示ひょうじπぱい(n)（藍あい）、n / ln (n)（綠みどり）與あずかLi(n)（紅べに）。

質しつ數すう計算けいさん函數かんすうπぱい(n)被ひ定義ていぎ為ため不ふ大だい於n的てき質しつ數すう之の數量すうりょう。例れい如，πぱい(11) = 5，因いん為ため有ゆう5個こ質しつ數すう小しょう於或等とう於11。已やめ知ち有ゆう演算えんざん法ほう可か比ひ去さ計算けいさん每ごと個こ不ふ大だい於n的てき質しつ數すう更さら快かい的まと速そく率りつ去さ計算けいさんπぱい(n)的てき值。質しつ數すう定理ていり表示ひょうじ，πぱい(n)的てき可か由よし下か列れつ公式こうしき近似きんじ給きゅう出で：

$\pi (n)\approx {\frac {n}{\ln n}},$

亦また即そく，πぱい(n)與あずか等式とうしき右邊うへん的てき值在n趨近於無限げん大時おおとき，會かい趨近於1。這表示ひょうじ，小しょう於n的てき數字すうじ為ため質しつ數すう的てき可能かのう性せい（大約たいやく）與あずかn的てき數すう位い呈てい正せい比ひ。對たいπぱい(n)更さら精確せいかく的てき描述可か由ゆかり對數たいすう積分せきぶん給きゅう出で：

$\operatorname {Li} (n)=\int _{2}^{n}{\frac {dt}{\ln t}}$。

質しつ數すう定理ていり亦また薀涵著ちょ對たい第だいn個こ質しつ數すうp_n（如p₁ = 2、p₂ = 3等とう）的てき大小だいしょう之の估算：當とう數字すうじ大だい到いた某ぼう一いち程度ていど時じ，p_n的てき值會變へん得え約やく略りゃく為ためn log(n)。特別とくべつ的てき是ぜ，質しつ數すう間隙かんげき，即そく兩個りゃんこ連續れんぞく質しつ數すうp_n與あずかp_n+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的てき等差とうさ數列すうれつ中ちゅう。

格かく林りん-陶とう定理ていり證明しょうめい，存在そんざい由よし任意にんい多た個こ質しつ數すう組成そせい的てき等差とうさ數列すうれつ。一いち個こ奇き質しつ數すうp可か表示ひょうじ成なり兩個りゃんこ平方へいほう數すう之の和わp = x² + y²，若わか且唯若わかp同どう餘よ於1模も4（费马平方和へいほうわ定理ていり）。

二次多項式的質數值

烏がらす嵐あらし螺旋らせん。紅べに點てん表示ひょうじ質しつ數すう。具ぐ4n² − 2n + 41形式けいしき的てき質しつ數すう則のり以藍點てん標記ひょうき。

歐おう拉ひしげ指出さしで函數かんすう

$n^{2}+n+41\,$

於　0 ≤ n < 40時どき會かい給きゅう出で質しつ數すう，此一事實導致了艱深的代數だいすう數すう論ろん，或ある更さら具體ぐたい地ち說せつ為ため黑くろ格納かくのう數すう。當とうn更さら大だい時じ，該函數すう會かい給きゅう出合であい數すう值。哈代- 李り特とく伍ご德とく猜想（Hardy-Littlewood conjecture）能のう給きゅう出で一いち個こ有ゆう關せき具ぐ整數せいすう係數けいすうa、b與あずかc的てき二に次じ多項式たこうしき

$f(n)=ax^{2}+bx+c\,$

的てき值為質しつ數すう之の機き率りつ的てき一個漸近預測，並なみ能のう以對數すう積分せきぶんLi(n)及係數すうa、b、c來らい表示ひょうじ。不ふ過か，該程式しき已やめ被ひ證あかし實じつ難なん以取得しゅとく：仍未知みち是ぜ否ひ存在そんざい一いち個こ二に次じ多項式たこうしき（a ≠ 0）能のう給きゅう出で無限むげん多た個こ質しつ數すう。烏がらす嵐あらし螺旋らせん將はた所有しょゆう自然しぜん數すう以螺旋らせん的てき方法ほうほう描繪。令れい人じん驚おどろき訝いぶか的てき是ぜ，質しつ數すう會かい群聚ぐんしゅう在ざい某ぼう些對角線たいかくせん上じょう，表示ひょうじ有ゆう些二次多項式會比其他二次多項式給出更多個質數值來。

未み解決かいけつ的てき問題もんだい

ζぜーた函數かんすう與あずか黎はじむ曼猜想そう

主しゅ条目じょうもく：黎はじむ曼猜想そう

ζぜーた函數かんすうζぜーた(s)的てき圖ず。在ざいs=1時じ，該函數すう會かい有ゆう極點きょくてん，亦また即そく會かい趨近於無限むげん大だい。

黎はじむ曼ζぜーた函數かんすうζぜーた(s)被ひ定義ていぎ為一ためいち無窮むきゅう級數きゅうすう

$\zeta (s)=\sum _{n=1}^{\infty }{\frac {1}{n^{s}}},$

其中，s為ため實數じっすう部分ぶぶん大だい於1的てき一いち個こ複數ふくすう。由よし算術さんじゅつ基本きほん定理ていり可か證しょう得え，該級數すう會かい等とう於下おした面めん的てき無窮むきゅう乘じょう積せき

$\prod _{p{\text{ prime}}}{\frac {1}{1-p^{-s}}}$。

ζぜーた函數かんすう與あずか質しつ數すう密みつ切きり相關そうかん。例れい如，存在そんざい無限むげん多た個こ質しつ數すう這個事實じじつ也可以使用しようζぜーた函數かんすう看み出で：若わか只ただ有ゆう有限ゆうげん多た個こ質しつ數すう，則のりζぜーた(1)將しょう會かい是ぜ個こ有限ゆうげん值。不ふ過か，調和ちょうわ級數きゅうすう1 + 1/2 + 1/3 + 1/4 + ...會かい發散はっさん，所以ゆえん必須ひっす有無うむ限げん多た個こ質しつ數すう。另一いち個こ能のう看み見みζぜーた函數かんすう的てき豐富ほうふ性せい，並なみ一瞥いちべつ現代げんだい代數だいすう數すう論ろん的てき例れい子こ為ため下面かめん的てき恆等こうとう式しき（巴ともえ塞ふさが爾しか問題もんだい，由ゆかり歐おう拉ひしげ給きゅう出で）：

$\zeta (2)=\prod _{p}{\frac {1}{1-p^{-2}}}={\frac {\pi ^{2}}{6}}$。

ζぜーた(2)的てき倒たおせ數すう6/πぱい²，是ぜ兩個りゃんこ隨ずい機き選定せんてい的てき數字すうじ會かい互質的てき機き率りつ。

未み被ひ證明しょうめい的てき「黎はじむ曼猜想そう」，於1859年ねん提出ていしゅつ，表示ひょうじ除じょs = −2, −4, ...,外そと，ζぜーた函數かんすう所有しょゆう的てき根ね，其實數すう部分ぶぶん均ひとし為ため1/2。此一猜想與質數間的關連在於，該猜想そう實際じっさい上じょう是ぜ在ざい說せつ，質しつ數すう在ざい正せい整數せいすう中ちゅう出現しゅつげん頻しき率りつ和わ統計とうけい學がく的てき隨ずい機き不同ふどう；若わか假設かせつ為真ためざに，質しつ數すう計算けいさん函數かんすう便びん可か有效ゆうこう掌握しょうあく，在ざい大數たいすう時じ不ふ再さい需要じゅよう近似きんじ求もとめ值。從したがえ物理ぶつり的てき觀點かんてん來らい看み，這大約やく是ぜ在ざい說せつ，質しつ數すう分ふん佈的不規則ふきそく性せい僅來自じ於隨機き的てき雜ざつ訊。從したがえ數學すうがく的てき觀點かんてん來らい看み，則のり大約たいやく是ぜ在ざい說せつ，質しつ數すう的てき漸近ぜんきん分ぶん佈（質しつ數すう定理ていり表示ひょうじ小しょう於x的てき質しつ數すう約やく有ゆうx/log x個こ）在ざいx周圍しゅうい的てき區間くかん內，於區間あいだ長ちょう度ど遠とお小しょう於x的てき平方根へいほうこん時じ亦また成立せいりつ。此一猜想一般認為是正確的。

其他猜想

更さら多た信しん息いき：分類ぶんるい:素數そすう猜想

除じょ了りょう黎はじむ曼猜想そう之の外そと，還かえ有ゆう許多きょた其他的てき猜想存在そんざい。雖然這些猜想的てき陳述ちんじゅつ大だい多た很簡單かんたん，但ただし許多きょた猜想經過けいか了りょう數すう十じゅう年ねん仍提不出ふしゅつ證明しょうめい，如4個こ蘭らん道どう問題もんだい，從したがえ1912年ねん提出ていしゅつ至いたり今こん仍然未み解かい。其中一いち個こ為ため哥德巴ともえ赫猜想そう，該猜想そう認みとめ為ため每ごと個こ大だい於2的てき偶數ぐうすうn都と可か表示ひょうじ成なり兩個りゃんこ質しつ數すう之の和わ。至いたり於2011年ねん2月がつ，這個猜想對たい最大さいだい達たちn = 2 · 10¹⁷的てき所有しょゆう數字すうじ都會とかい成立せいりつ。較弱形式けいしき的てき哥德巴ともえ赫猜想そう已やめ被ひ證明しょうめい，如維諾格かく拉ひしげ多た夫おっと定理ていり，該定理ていり表示ひょうじ每ごと個こ足あし夠大的てき奇數きすう都と可か表示ひょうじ成なり三さん個こ質しつ數すう之の和わ。陈氏定理ていり表示ひょうじ，每まい個こ足あし夠大的てき偶數ぐうすう都と可か表示ひょうじ成なり一いち個こ質しつ數すう與一よいち個こ半はん質しつ數すう（兩個りゃんこ質しつ數すう的てき乘じょう積せき）之の和わ。此外，任にん一個偶數均可寫成六個質數之和。數かず論ろん研究けんきゅう這些問題もんだい的てき分ぶん支ささえ稱しょう之の為ため加法かほう數すう論ろん。反はん哥德巴ともえ赫猜想おもえ，所有しょゆう的てき正せい偶數ぐうすうn都と可か以表示ひょうじ成なり兩個りゃんこ質しつ數すう之これ差さ，但ただし此猜想そう可か由よし波は利り尼あま亞あ克かつ猜想類推るいすい證明しょうめい。

其他猜想處理しょり是ぜ否ひ有無うむ限げん多た個こ具ぐ某ぼう些限制せい的てき質しつ數すう這類問題もんだい。據よりどころ猜想，存在そんざい無限むげん多た個こ費ひ波なみ那な契ちぎり質しつ數すう與あずか無限むげん多た個こ梅森うめもり質ただし數すう，但ただし沒ぼっ有無うむ限げん多た個こ費ひ馬ば質しつ數すう。還かえ不ふ知道ともみち是ぜ否ひ存在そんざい無限むげん多た個こ維費里さと希まれ質しつ數すう與あずか歐おう幾里いくさと得とく質しつ數すう。

第だい三種類型的猜想涉及到質數的分佈情形。據よりどころ猜想，存在そんざい無限むげん多おお對たい孿生質しつ數すう，即そく有無うむ限げん多た對たい相差おうさつ2的てき質しつ數すう（孿生質しつ數すう猜想）。波なみ利り尼あま亞あ克かつ猜想是ぜ比ひ孿生質しつ數すう猜想更さら強的ごうてき一いち個こ猜想，該猜想そう表示ひょうじ存在そんざい無限むげん多おお對たい相差おうさつ2n的てき連續れんぞく質しつ數すう。據よりどころ猜想，存在そんざい無限むげん多た個こ具ぐn² + 1形式けいしき的てき質しつ數すう。上述じょうじゅつ猜想都と是ぜ申さる策さく爾しか猜想的てき特例とくれい。布ぬの羅ら卡猜想そう表示ひょうじ，在ざい兩個りゃんこ大だい於2的てき連續れんぞく質しつ數すう之の平方へいほう數すう之の間あいだ，總そう是ぜ會かい有ゆう至いたり少しょう4個こ質しつ數すう。勒讓德とく猜想表示ひょうじ，對たい每まい個こ正せい整數せいすうn，n²與あずか(n + 1)²間あいだ總會そうかい存在そんざい一いち個こ質しつ數すう。克かつ拉ひしげ梅うめ爾なんじ猜想可か導出どうしゅつ勒讓德とく猜想。

應用おうよう

長期ちょうき以來いらい，數かず論ろん，尤ゆう其是對質たいしつ數すう的てき研究けんきゅう，一般都會被認為是典型的純數學，除じょ了りょう求もとめ知的ちてき趣味しゅみ之の外そと，沒ぼつ有ゆう其他應用おうよう。特別とくべつ是ぜ，一いち些數論ろん學がく家か，如英國えいこく數學すうがく家か戈ほこ弗どる雷かみなり·哈羅德とく·哈代即そく對たい其工作こうさく絕對ぜったい不ふ會かい有ゆう任にん何なん在ざい軍事ぐんじ上じょう的てき重大じゅうだい性感せいかん到いた自じ豪ごう。然しか而，此一觀かん點在てんざい1970年代ねんだい時じ遭到粉碎ふんさい，當とう質しつ數すう被ひ公開こうかい宣布せんぷ可か以作為さくい產さん生せい公おおやけ鑰加密みつ演算えんざん法的ほうてき基礎きそ之の時とき。質しつ數すう現在げんざい也被用よう在ざい雜ざつ湊みなと表ひょう與あずか偽にせ亂數らんすう產さん生せい器き裡うら。

旋轉せんてん機き被ひ設計せっけい成なり在ざい每まい個こ轉てん片上かたがみ有ゆう不ふ同數どうすう目的もくてき銷，在ざい每まい個こ轉てん片上かたがみ的てき銷的數量すうりょう都會とかい是ぜ質しつ數すう，亦また或ある是ぜ會かい與あずか其他轉てん片上かたがみ的てき銷的數量すうりょう互質。這有助じょ於在重じゅう復ふく所有しょゆう的てき組合くみあい之の前まえ，讓ゆずる所有しょゆう轉てん片へん的てき可能かのう組合くみあい都と能のう出現しゅつげん過か一いち次じ。

國際こくさい標準ひょうじゅん書しょ號ごう的てき最後さいご一いち碼為校こう驗けん碼，其演算法さんぽう使用しよう到いた了りょう11是これ個こ質しつ數すう的てき這個事實じじつ。

在ざい汽車きしゃ變速へんそく箱ばこ齒は輪わ的てき設計せっけい上じょう，相あい鄰的兩個りゃんこ大小だいしょう齒ぱ輪わ齒ぱ数すう最さい好こう設計せっけい成なり素数そすう，以增加ぞうか兩りょう齒は輪わ內兩個りゃんこ相しょう同どう的てき齒は相しょう遇ぐう嚙合次数じすう的てき最小公倍数さいしょうこうばいすう，可か增強ぞうきょう耐たい用度ようど減少げんしょう故障こしょう。

在ざい害蟲がいちゅう的てき生物せいぶつ生長せいちょう周期しゅうき與あずか殺蟲さっちゅう劑ざい使用しよう之の間あいだ的てき關係かんけい上じょう，殺蟲さっちゅう劑ざい的てき素数そすう次数じすう的てき使用しよう也得到いた了りょう證明しょうめい。實驗じっけん表明ひょうめい，素数そすう次数じすう地ち使用しよう殺蟲さっちゅう劑ざい是ぜ最さい合理ごうり的てき：都みやこ是ただし使用しよう在ざい害蟲がいちゅう繁殖はんしょく的てき高潮こうちょう期き，而且害蟲がいちゅう很難産なんざん生せい抗こう藥くすり性せい。

以素数すう形式けいしき无规律りつ变化的てき导弹和わ鱼雷可か以使敌人不易ふえき拦截。

模かたぎ一質數與有限體之運算

主しゅ条目じょうもく：模かたぎ運算うんざん

「模かたぎ運算うんざん」使用しよう下か列れつ數字すうじ修おさむ改あらため了りょう一般いっぱん的てき運算うんざん

$\{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\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\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\cdot x\equiv 2\ \ (\operatorname {mod} \ 7),$

會かい有ゆう唯一ゆいいつ的てき解かいx = 3。因よし此，對たい任にん何なん質しつ數すうp，Z/pZ（亦また標記ひょうき為ためF_p）也會是これ個こ體からだ，或ある更さら具體ぐたい地ち說せつ，是これ個こ有限ゆうげん體たい，因いん為ため該集合しゅうごう包含ほうがん有限ゆうげん多た（即そくp）個こ元素げんそ。

許多きょた定理ていり可か以透過とうか從したがえ此一抽象的方式檢查F_p而導出どうしゅつ。例れい如，費ひ馬ば小しょう定理ていり表示ひょうじ

$a^{p-1}\equiv 1(\operatorname {mod} \ p)$

，其中a為ため任にん一いち不ふ被ひp整除せいじょ的てき整數せいすう。該定理ていり即そく可か使用しよう這些概念がいねん證しょう得とく。這意味あじ著ちょ

$\sum _{a=1}^{p-1}a^{p-1}\equiv (p-1)\cdot 1\equiv -1{\pmod {p}}$。

吾鄉あごう-朱しゅ加か猜想表示ひょうじ，上述じょうじゅつ公式こうしき亦また是ぜp為ため質しつ數すう的てき必要ひつよう條件じょうけん。另一個費馬小定理的推論如下：若わかp為ため2與あずか5之の外的がいてき其他質しつ數すう，¹/_p總そう是ぜ個こ循環じゅんかん小數しょうすう，其週期き為ためp − 1或あるp − 1的てき因數いんすう。分數ぶんすう¹/_p依よq（10以外いがい的てき整數せいすう）為ため基底きてい表示ひょうじ亦また有ゆう類似るいじ的てき效果こうか，只ただ要ようp不ふ是ぜq的てき質しつ因數いんすう的てき話ばなし。威い爾しか遜へりくだ定理ていり表示ひょうじ，整數せいすうp > 1為ため質しつ數すう，若わか且唯若わか階かい乘じょう (p − 1)! + 1可か被ひp整除せいじょ。此外，整數せいすうn > 4為ため合ごう數すう，若わか且唯若わか (n − 1)!可か被ひn整除せいじょ。

其他數學すうがく裡うら出現しゅつげん的てき質しつ數すう

許多きょた數學すうがく領域りょういき裡うら會かい大量たいりょう使用しよう到いた質しつ數すう。舉有限ゆうげん群ぐん的てき理論りろん為ため例れい，西にし羅ら定理ていり即そく是ぜ一いち例れい。該定理ていり表示ひょうじ，若わかG是ぜ個こ有限ゆうげん群ぐん，且pⁿ為ため質しつ數すうp可か整除せいじょG的てき階かい的てき最大さいだい冪べき次じ，則のりG會かい有ゆう個こpⁿ階かい的てき子こ群ぐん。此外，任意にんい質しつ數すう階かい的てき群ぐん均ひとし為ため循環じゅんかん群ぐん（拉ひしげ格かく朗ろう日び定理ていり）。

公開こうかい金きん鑰加密みつ

主しゅ条目じょうもく：公開こうかい金きん鑰加密みつ

幾いく個こ公開こうかい金きん鑰加密みつ演算えんざん法ほう，如RSA與あずか迪すすむ菲－赫爾曼金鑰交換こうかん，都みやこ是ただし以大質しつ數すう為ため其基礎きそ（如512位い元もと的てき質しつ數すう常つね被ひ用よう於RSA裡うら，而1024位い元もと的てき質しつ數すう則のり一般被迪菲-赫爾曼金鑰交換こうかん所しょ採用さいよう）。RSA依よ靠もたれ計けい算出さんしゅつ兩個りゃんこ（大だい）質しつ數すう的てき相乘そうじょう會かい比ひ找出相乘そうじょう後ご的てき數すう的てき兩個りゃんこ質しつ因數いんすう容易ようい出で許多きょた這個假設かせつ。迪すすむ菲－赫爾曼金鑰交換こうかん依よ靠もたれ存在そんざい模かたぎ冪べき次じ的てき有效ゆうこう演算えんざん法ほう，但ただし相反あいはん運算うんざん的てき離散りさん對數たいすう仍被認みとめ為ため是ぜ個こ困難こんなん的てき問題もんだい此一事實じじつ。

自然しぜん裡うら的てき質しつ數すう

周期しゅうき蟬屬ぞく裡うら的てき蟬在ざい其演化か策略さくりゃく上じょう使用しよう到いた質しつ數すう。蟬會在地ざいち底そこ下か以幼蟲ようちゅう的形まとがた態度たいど過か其一生せい中ちゅう的てき大だい部分ぶぶん時間じかん。周期しゅうき蟬只會かい在ざい7年ねん、13年ねん或ある17年ねん後ご化か蛹さなぎ，然しか後ご從したがえ洞穴どうけつ裡うら出現しゅつげん、飛行ひこう、交配こうはい、產卵さんらん，並なみ在ざい至いたり多數たすう週しゅう後ご死亡しぼう。此一演化策略的原因據信是因為若出現的週期為質數年，掠かすめ食しょく者しゃ就很難なん演えんじ化成かせい以周期き蟬為主食しゅしょく的てき動物どうぶつ。若わか周期しゅうき蟬出現しゅつげん的てき週しゅう期き為ため非ひ質しつ數すう年ねん，如12年ねん，則のり每ごと2年ねん、3年ねん、4年ねん、6年ねん或ある12年ねん出現しゅつげん一次的掠食者就一定遇得到周期蟬。經過けいか200年ねん以後いご，假設かせつ14年ねん與あずか15年ねん出現しゅつげん一いち次じ的てき周期しゅうき蟬，其掠食しょく者しゃ的てき平均へいきん數量すうりょう，會かい比ひ13年ねん與あずか17年ねん出現しゅつげん一いち次じ的てき周期しゅうき蟬，高こう出で2%。雖然相差おうさつ不ふ大だい，此一優勢似乎已足夠驅動天擇，選擇せんたく具ぐ質しつ數すう年ねん生命せいめい週しゅう期き的てき這些昆蟲こんちゅう。

據よりどころ猜測，ζぜーた函數かんすう的てき根ね與あずか複數ふくすう量子りょうし系統けいとう的てき能のう階かい有ゆう關せき。

推廣

質しつ數すう的てき概念がいねん是ぜ如此的てき重要じゅうよう，以致此一概念被以不同方式推廣至數學的不同領域裡去。通常つうじょう，「質しつ」（prime）可か在ざい適當てきとう的てき意義いぎ下か，用よう來らい表示ひょうじ具有ぐゆう最小さいしょう性せい或ある不可ふか分解ぶんかい性せい。例れい如，質しつ體たい是ぜ指ゆび一いち個こ包含ほうがん0與あずか1的てき體からだF的てき最小さいしょう子こ體たい。質しつ體たい必為有理數ゆうりすう或ある具有ぐゆうp個こ元素げんそ的てき有限ゆうげん體たい，這也是ぜ其名稱めいしょう的てき緣由えんゆ。若わか任にん一物件基本上均可唯一地分解成較小的部分，則のり這些較小的てき部分ぶぶん也會用よう「質しつ」這個字じ來らい形容けいよう。例れい如，在ざい紐ひも結ゆい理論りろん裡うら，質しつ紐ひも結ゆい是ぜ指ゆび不可ふか分解ぶんかい的てき紐ひも結ゆい，亦また即そく該紐結ゆい不可ふか寫うつし成なり兩個りゃんこ非ひ平凡へいぼん紐ひも結ゆい的てき連れん通どおり和わ。任にん一紐結均可唯一地表示為質紐約的連通和。質しつ模型もけい與あずか三さん維質流りゅう形がた亦また為ため此類型がた的てき例れい子こ。

環かん內的素もと元もと

主しゅ条目じょうもく：素もと元もと和わ不可ふか約やく元素げんそ

質しつ數すう應用おうよう於任一いち可か交換こうかん環たまきR（具ぐ加法かほう、減法げんぽう與あずか乘法じょうほう的てき代數だいすう結構けっこう）的てき元素げんそ，可か產さん生せい兩個りゃんこ更さら為ため一般いっぱん的てき概念がいねん：「素もと元もと」與あずか「不可ふか約やく元素げんそ」。R的てき元素げんそ稱しょう為ため素もと元もと，若わか該元素げんそ不為ふため0或ある單位たんい元素げんそ，且給定じょうR內的元素げんそx與あずかy，若わかp可か除じょ以xy，則のりp可か除じょ以x或あるy。一元素稱為不可約元素，若わか該元素げんそ不為ふため單位たんい元素げんそ，且無法ほう寫うつし成なり兩個りゃんこ不ふ是ぜ單位たんい元素げんそ之の環かん元素げんそ的てき乘じょう積せき。在ざい整數せいすう環たまきZ裡うら，由ゆかり素もと元もと所しょ組成そせい的てき集合しゅうごう等とう於由不可ふか約やく元素げんそ所しょ組成そせい的てき集合しゅうごう，為ため

$\{\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)、…算術さんじゅつ基本きほん定理ていり被ひ廣義こうぎ化成かせい準じゅん素もと分解ぶんかい，可か將しょう每ごと個こ在ざい可か交換こうかん諾だく特とく環たまき裡うら的てき理想りそう表示ひょうじ成なり準じゅん素もと理想りそう（為ため質しつ數すう冪べき次じ的てき一いち適合てきごう廣義こうぎ化か）的てき交集。

透過とうか環たまき的てき譜ふ這個概念がいねん，質しつ理想りそう成なり為ため代數だいすう幾何きか物件ぶっけん的てき點てん。算術さんじゅつ幾何きか也受益えき於這個こ概念がいねん，且許多た概念がいねん會同かいどう時じ存在そんざい於幾おき何なに與あずか數すう論ろん之の內。例れい如，對たい一いち擴張かくちょう體たい的てき質しつ理想りそう分解ぶんかい（這是代數だいすう數すう論ろん裡うら的てき一いち個こ基本きほん問題もんだい），與あずか幾何きか裡うら的てき分ぶん歧具有ぐゆう某ぼう些相似そうじ之の處しょ。此類分ぶん歧問題もんだい甚至在ざい只ただ關せき注ちゅう整數せいすう的てき數すう論ろん問題もんだい裡うら也會出現しゅつげん。例れい如，二に次じ體たい的てき整數せいすう環たまき內的質しつ理想りそう可か被ひ用もちい來らい證明しょうめい二に次じ互反律りつ。二次互反律討論下面二次方程

$x^{2}\equiv p\ \ ({\text{mod }}q),\,$

是ぜ否いや有ゆう整數せいすう解かい，其中x為ため整數せいすう，p與あずかq為ため（一般いっぱん）質しつ數すう。早期そうき對たい費ひ馬ば最後さいご定理ていり證明しょうめい之の嘗試，於恩おん斯特·庫こ默だま爾しか引入正則せいそく素數そすう後こう達たち到いた了りょう高潮こうちょう。正則せいそく質しつ數すう是ぜ指ゆび無法むほう在ざい由よし下か列れつ式子しょくし（其中a₀、…、a_p−1為ため整數せいすう，ζぜーた則のり是能これよし使しζぜーた^p = 1的てき複數ふくすう）

$a_{0}+a_{1}\zeta +\cdots +a_{p-1}\zeta ^{p-1}\,,$

組成そせい的てき環たまき裡うら，使つかい得とく唯一ゆいいつ分解ぶんかい定理ていり失效しっこう的てき質しつ數すう。

賦ふ值

賦ふ值理論ろん研究けんきゅう由よし一いち個體こたいK映うつ射い至いたり實數じっすうR的てき某ぼう個こ函數かんすう（稱しょう之の為ため賦ふ值）。每まい個こ此類賦ふ值都能のう給きゅう出で一いち個こ K上うえ的てき拓ひらけ撲なぐ，且兩個りゃんこ賦ふ值被稱しょう為ため等價とうか，若わか兩者りょうしゃ有ゆう相しょう同どう拓ひらけ撲なぐ。K的てき質しつ數すう為ため一いち賦ふ值的等價とうか類るい。例れい如，一いち個こ有理數ゆうりすうq的てきp進すすむ賦ふ值被ひ定義ていぎ為ため整數せいすうv_p(q)，使つかい得とく

$q=p^{v_{p}(q)}{\frac {r}{s}},$

其中r與あずかs不ふ被ひp所しょ整除せいじょ。例れい如，v₃(18/7) = 2。p進すすむ範はん數すう被ひ定義ていぎ為ため

$\left|q\right|_{p}:=p^{-v_{p}(q)}.\,$

特別とくべつ的てき是ぜ，當とう一いち個こ數字すうじ乘じょう上じょうp時とき，其範數すう會かい變へん小しょう，與一よいち般的絕對ぜったい賦ふ值（亦また稱たたえ為ため無限むげん質しつ數すう）形成けいせい明あかり顯あらわ的てき對比たいひ。當とう透過とうか絕對ぜったい賦ふ值完備かんび有理數ゆうりすう會得えとく出で由ゆかり實數じっすう所ところ組成そせい的てき體からだ，透過とうかp進すすむ範はん數すう完備かんび有理數ゆうりすう則そく會得えとく出で由ゆかりp進數しんすう所ところ組成そせい的てき體からだ。實際じっさい上じょう，依據いきょ奧おく斯特洛らく夫おっと斯基定理ていり，上述じょうじゅつ兩りょう種たね方法ほうほう是ぜ完備かんび有理數ゆうりすう的てき所有しょゆう方法ほうほう。一些與有理數或更一般化之大域たいいき體たい有ゆう關せき的てき算術さんじゅつ問題もんだい，可能かのう可か以被轉換てんかん至いたり完備かんび（或ある局部きょくぶ）體からだ上じょう。此一局部きょくぶ-全域ぜんいき原則げんそく再さい次つぎ地ち強調きょうちょう了りょう質しつ數すう對たい於數論ろん的てき重要じゅうよう性せい。

在ざい藝術げいじゅつ與あずか文學ぶんがく裡うら

質しつ數也かずや影響えいきょう了りょう許多きょた的てき藝術げいじゅつ家か與作よさく家か。法ほう國こく作曲さっきょく家か奧おく立佛たちぼとけ·梅うめ湘使用しよう質しつ數すう創造そうぞう出で無む節ふし拍はく音樂おんがく。在ざい《La Nativite du Seigneur》與あずか《Quatre etudes de rythme》等とう作品さくひん裡うら，梅うめ湘同時じ採用さいよう由よし不ふ同質どうしつ數すう給きゅう定之さだゆき長ちょう度ど的てき基調きちょう，創造そうぞう出で不可ふか預あずか測はか的てき節奏せっそう：第だい三さん個こ練習れんしゅう曲きょく《Neumes rythmiques》中ちゅう出現しゅつげん了りょう質しつ數すう41、43、47及53。據よりどころ梅うめ湘所述じゅつ，此類作曲さっきょく方式ほうしき是ぜ「由よし自然しぜん的てき運動うんどう，自由じゆう且不均ひとし勻的持續じぞく運動うんどう中ちゅう獲得かくとく的てき靈感れいかん」。

NASA科學かがく家か卡爾·薩根在ざい他た的てき科か幻まぼろし小說しょうせつ《接觸せっしょく未來みらい》（Contact）裡うら，認みとめ為ため質しつ數すう可か作為さくい與あずか外そと星ほし人じん溝みぞ通どおり的てき一いち種しゅ方式ほうしき。這種想そう法ほう是ぜ他た與あずか美國びくに天文學てんもんがく家か法ほう蘭らん克かつ·德とく雷かみなり克かつ於1975年閒ねんかん聊時形成けいせい的てき。

許多きょた電でん影かげ，如《異い次元じげん殺陣さつじん》（Cube）、《神かみ鬼おに尖兵せんぺい》（Sneakers）、《越こし愛あい越こし美麗みれい》（The Mirror Has Two Faces）及《美麗びれい境界きょうかい》（A Beautiful Mind），均ひとし反映はんえい出で大だい眾對質たいしつ數すう與あずか密みつ碼學之の神秘しんぴ的てき迷戀。保ほ羅ら·裘唐諾だく所ところ著ちょ的てき小說しょうせつ《質しつ數すう的てき孤獨こどく》（The Solitude of Prime Numbers）裡うら，質しつ數すう被ひ用よう來らい比ひ喻寂寞與孤獨こどく，被ひ描述成なり整數せいすう之の間あいだ的てき「局外きょくがい人じん」。

荒木あらき飛ひ呂りょ彥所創作そうさく的てき日本にっぽん漫畫まんが《JoJo的てき奇妙きみょう冒險ぼうけん》第だい六ろく部ぶ《石いし之の海うみ》的てき反はん派は普ひろし奇き神父しんぷ喜き歡數質しつ數すう，他た認みとめ為ため質しつ數すう是ぜ孤獨こどく的てき數字すうじ，並なみ透過とうか數すう質しつ數すう安やす撫なで他た緊張きんちょう的てき情緒じょうちょ。

另見

• 阿おもね德とく曼-波なみ門もん倫りん斯-魯梅利り質しつ數すう測はか試ためし
• Bonse不等式ふとうしき
• 布ぬの朗ろう篩ふるい法ほう
• 伯はく恩おん賽さい德とく定理ていり
• 契ちぎり博はく塔とう耶夫密度みつど定理ていり
• 中國ちゅうごく餘あまり數すう定理ていり
• 卡倫數すう
• 非ひ法ほう質しつ數すう
• 質しつ數列すうれつ表ひょう
• 梅森うめもり質ただし數すう
• 可か乘數じょうすう論ろん
• 普通ふつう數すう域いき篩ふるい選せん法ほう
• 貝かい潘はん測はか試ためし
• 實際じっさい數すう
• 質しつk元もと組くみ
• 自由じゆう黎はじむ曼氣體きたい
• 二に次じ剩餘じょうよ問題もんだい
• RSA數すう
• 光ひかり滑すべり數すう
• 超ちょう質しつ數すう
• 胡えびす道どう爾なんじ數すう
• 幸こう运素数すう
• 素数そすう判定はんてい法ほう则
• 埃ほこり拉ひしげ托たく斯特尼あま筛法
• 孪生素数そすう
• 三さん胞胎素数そすう
• PrimeGrid
• GIMPS
• 質しつ數すう大だい富豪ふごう

參考さんこう資料しりょう

• 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)的てき《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 （页面存そん档备份，存そん于互联网档案あん馆）
• 素数そすう发生器き和わ校こう验器 （页面存そん档备份，存そん于互联网档案あん馆）