什麼是質數? 試找出1-100以內的質數

素數，又稱質數，是只有兩個正因數（1和自己）的自然數。

比1大但不是質數的數稱之為合數，而1和0既非質數也非合數。質數的屬性稱為素性，質數在數論中有著非常重要的地位。

關於質數
最小的質數是2，而最大的質數並不存在，這一點歐幾里德已在其《幾何原本》中證明。

圍繞質數存在很多的數學問題、數學猜想、數學定理，較為著名的有孿生質數猜想、哥德巴赫猜想等等。

1-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

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

所謂質數或稱素數，就是一個正整數，除了本身和 1 以外並沒有任何其他因子。例如 2，3，5，7 是質數，而 4，6，8，9 則不是，後者稱為合成數。從這個觀點可將整數分為兩種，一種叫質數，一種叫合成數。（有人認為數目字 1 不該稱為質數）著名的高斯「唯一分解定理」說，任何一個整數。可以寫成一串質數相乘的積。例如
圖片參考：http://episte.math.ntu.edu.tw/articles/mm/mm_04_4_04/img6.gif
，這就是說，任何數都由質數構成的。
我們研究質數一方面是為了簡單，我們可以找到數字的原子。
當然另一方面也由於質數本身的奇異性使人無法一把抓住它出現的規律，抓住它出現的特性甚至不知道它實際分佈的情形。簡單來說，給你一個正整數，你竟不可知道它是否是一個質數你說它狡猾不狡猾，即使你用盡了方法，證明它不可能是一個質數，但竟無法分解它，你說怎辦？舉例來說吧！ 211-1=2047 可以分解成
圖片參考：http://episte.math.ntu.edu.tw/articles/mm/mm_04_4_04/img7.gif
。267-1 呢？據說化費了美國代數學家 Frank Neloon Cole(1861-1927)三年多才發現的。自然那時「電腦時代」還未來臨，只能靠無限的耐心與毅力，再加上一副長於計算數目的訓練才弄得出來。但有了電腦又怎樣呢？
似乎好不了多少，數目字加大了，困難依舊。1931年 D.H. Lehmar 證明了 2257-1 是一個大合成數。大！不錯。它等於


圖片參考：http://episte.math.ntu.edu.tw/articles/mm/mm_04_4_04/img8.gif



一個78位數字的大數，到目前仍未有人或電腦能分解它！
因此，雖然知道一個數目是否質數也許沒有多大用處，但仍是很有趣味，最少在找它的過程中會引起很多方法論的問題呢!




(二)找質數
怎樣找質數呢？這個問題據說自希臘及中國周朝已有人在問這個難題了。下面是一些初步查詢。
質數是無窮。這很早就證明了。因若 p1=2, p2=3,
圖片參考：http://episte.math.ntu.edu.tw/articles/mm/mm_04_4_04/img9.gif
, pn 中任一個質數的新質數所除盡，故而 pn+1 存在了；且


圖片參考：http://episte.math.ntu.edu.tw/articles/mm/mm_04_4_04/img11.gif




舉例說，



圖片參考：http://episte.math.ntu.edu.tw/articles/mm/mm_04_4_04/img12.gif



但


30031=59 x 509



證明了
圖片參考：http://episte.math.ntu.edu.tw/articles/mm/mm_04_4_04/img13.gif
，不必是質數。
考慮


圖片參考：http://episte.math.ntu.edu.tw/articles/mm/mm_04_4_04/img14.gif




f(n) 形式中是否有無限個質數存在或 f(p) 中是否有無限合成數存在呢？
怎樣證明 n 是一個質數呢？
傳統的「篩法」是將任一個數n的可能因子查證，簡化後；只要過濾所有小於
圖片參考：http://episte.math.ntu.edu.tw/articles/mm/mm_04_4_04/img18.gif
可開平方成整數。因而 x=34, y=15，即 u=19,v=49，即 N=931=19 x 49，即是一個合成數。








(三)質數方程式
上節所談到的函數
圖片參考：http://episte.math.ntu.edu.tw/articles/mm/mm_04_4_04/img19.gif
，我們期望找到一個類似的函數，對任何變數值（一個整數），我們得到的f(n)函數值皆是質數。即是我們

對所有整數 n, f(n)= 質數, n=0,1,2,…












(A)多項式的質數方程
若這多項是 0 次的，那麼 f(n)=p 雖滿足所求，但一無用處，故可以不論。若這多項式是一次的，那麼 f(n)=an+b。要這個方程式成功，an+b 一定是一個算術級數（等差級數），例如


圖片參考：http://episte.math.ntu.edu.tw/articles/mm/mm_04_4_04/img20.gif



但當 n=4 時，f(4)=9，便不是了。較長一點的

199,409,619,829,1039, 1249,1459, 1669, 1879,2089.


都是質數，方程式為 f2(n)=210n+199, n=0,1,2,…,9 很顯然 n=199 時一定不是質數，事實上，還不用那麼大，n=10 時 f(10)=2100+199=2299，可被11除盡。
這說明了不可能有一串都是質數的算術級數。事實上，若果
圖片參考：http://episte.math.ntu.edu.tw/articles/mm/mm_04_4_04/img24.gif
。
結論是，沒有一個像an+b樣子的函數可以包含全是質數的。也許轉來問一下，這樣形式的質數是否無窮呢？
Dirichlet（Dirichlet 定理，可在《數論導引》中第九章找到證明。）曾證明，若
圖片參考：http://episte.math.ntu.edu.tw/articles/mm/mm_04_4_04/img9.gif
但是在 (6n+3) 中只有一個 3 是質數，而在 6n+4 中沒有一個質數。一般說來，如 p 不是 a 的因子，則形如 an+b 的數列每隔 p 項便有一個為 p 除盡的數了。如上文 f(n)=210n+199，可見 11 不是 210 因子，即每隔 11 項一定有一個 11 可除盡的項了。由這條定理看來。要求長一點的連續質數數列也不太容易，目前知，如


圖片參考：http://episte.math.ntu.edu.tw/articles/mm/mm_04_4_04/img26.gif



含連續 12 個質數已是很長了。例如 f(x)=x2-2999x+2248541，由 1460 到 1539 的 x 值一共連結有 80 個使 f(x) 函數值是質數。一次方程式既不可能，不妨找二次方程式試試：在形式如 ax2+bx+c=f(x) 中，我們也找到不少。


圖片參考：http://episte.math.ntu.edu.tw/articles/mm/mm_04_4_04/img27.gif



當然，我們可以無限的追求下去，但很顯然 ax2+bx+c 不可能永遠是質數，因如 ax02+bx0+c=p，則 xk=x0+kp 一定得為 p 整除，也是說 {an2+bn+c} 這個數到每隔 p 項一定被 p 整除。同樣理由也可以推廣到三次多項式，如
圖片參考：http://episte.math.ntu.edu.tw/articles/mm/mm_04_4_04/img28.gif
。但是，類似在一次多項式中的 Dirichlet 定理，證明 an2+bn+c 形式有無限的質數存在的定理，還未存在，所以我們並不能知道上述任何一個以二次多項式所表示出來的數列中具有無限多的質數。
連最簡單的 n2+1 的形式中是否含有無限多質數我們都不知道，雖然 2,5,17,37,101
圖片參考：http://episte.math.ntu.edu.tw/articles/mm/mm_04_4_04/img9.gif
等都是。目前僅知道的是，有無限個 (n2+1) 形式的數具有最多三個質數因子而已。推廣這類多項式到高次；可以參考 Halberstam and Richert 在1975年出版的《篩法》(Sieve methods, Academic Press)。
不過，所謂求一條長的質數數列是一件難事，端指我們希望找到一個多項式 f(n)，使 f(n) 能帶給我們「很多」（更好是全部都是）新的質數。即找出我們仍未知道的質數。
若僅僅為了一條長長的質數數列，那麼從已知的質數推出來，竟是一件輕而易舉之事，例如我們可以逆推之。例如要使得 f(0)=3,f(1)=5,f(2)=7,f(3)=11 則 3f(n)=n3-3n2+8n+9 便可以了。若要使得 f(0)=3, f(1)=5, f(2)=7, f(3)=11, f(4)=13, f(5)=17，則 60f(n) = 7n5-85n4 + 355n3 - 575n2 + 418n + 180 才可以。換言之，若要求出一個含有 100 個已知的連續（任何已知的！）質數數列的多項式，只要依樣就可以製造出一個 101 次的多項式出來，
圖片參考：http://episte.math.ntu.edu.tw/articles/mm/mm_04_4_04/img29.gif
只是，這些多項式一無用處。並不帶給我們任何新的質數。
我們主要目的在於找出一條能供應我們無限多的新鮮的質數的「方程式」來。上述的所有質數多項式完全不能符合這個需要，因為代入 n 值以後，我們還無法知道得出的是否為一個質數呢！（更別談它是否有無窮個如此形狀的質數了？）例如 n2+1 多項式，究竟 n=1010，是否出現質數，n=123456789 呢？這還要乞靈電腦去查呢！

質數
維基百科，自由的百科全書
(重定向自質數)
跳转到： 导航, 搜索
素數，又稱質數，一個大於1的整數中，除了1和此整數自身外，沒法被其他數整除的自然數；即是只有兩個正因數（1和自己）的自然數。

比1大但不是質數的數稱之為合數又稱合成數，而1和0既非質數也非合數。質數的屬性稱為素性，質數在數論中有著非常重要的地位。

目錄 [隱藏]
1 關於質數
2 質數的數目
3 尋找質數
4 檢驗質數
5 未解之謎
6 質數的應用
7 外部連結



[編輯] 關於質數
最小的質數是2，也是唯一偶數(雙數),其他都是奇數(單數)而最大的質數並不存在，因有無限多，這一點歐幾里德已在其《幾何原本》中證明。

圍繞質數存在很多的數學問題、數學猜想、數學定理，較為著名的有孿生質數猜想、哥德巴赫猜想等等。

質數序列的開頭是這樣：

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 (OEIS:A000040)
質數集合有時也被表示成粗體 。

在抽象代數的一個分支－環論中，素元素有特殊的含義，在這個含義下，任何質數的加法的逆轉也是質數。換句話說，將整數Z的集合看成是一個環，-Z是一個素元素。不管怎樣，數學領域內，提到質數通常是指正質數。

算術基本定理說明每個正整數都可以寫成質數的乘積，因此質數也被稱為自然數的「建築的基石」例如：


關於分解的詳細方法，可見於整數分解這條目。

這個定理的重要一點是，將1排斥在質數集合以外。如果1被認為是質數，那麼這些嚴格的闡述就不得不加上一些限制條件了。

0由於可以被任何數整除(因餘數一定等於0),所以它不符合素數的定義。

所謂質數或稱素數，就是一個正整數，除了本身和 1 以外並沒有任何其他因子。例如 2，3，5，7 是質數，而 4，6，8，9 則不是，後者稱為合成數。從這個觀點可將整數分為兩種，一種叫質數，一種叫合成數。（有人認為數目字 1 不該稱為質數）著名的高斯「唯一分解定理」說，任何一個整數。可以寫成一串質數相乘的積。例如 ，， ， ， ， ，這就是說，任何數都由質數構成的。

我們研究質數一方面是為了簡單，我們可以找到數字的原子。

當然另一方面也由於質數本身的奇異性使人無法一把抓住它出現的規律，抓住它出現的特性甚至不知道它實際分佈的情形。簡單來說，給你一個正整數，你竟不可知道它是否是一個質數你說它狡猾不狡猾，即使你用盡了方法，證明它不可能是一個質數，但竟無法分解它，你說怎辦？舉例來說吧！ 211-1=2047 可以分解成 。267-1 呢？據說化費了美國代數學家 Frank Neloon Cole(1861-1927)三年多才發現的。自然那時「電腦時代」還未來臨，只能靠無限的耐心與毅力，再加上一副長於計算數目的訓練才弄得出來。但有了電腦又怎樣呢？

似乎好不了多少，數目字加大了，困難依舊。1931年 D.H. Lehmar 證明了 2257-1 是一個大合成數。大！不錯。它等於一個78位數字的大數，到目前仍未有人或電腦能分解它！
因此，雖然知道一個數目是否質數也許沒有多大用處，但仍是很有趣味，最少在找它的過程中會引起很多方法論的問題呢!



100 以內質數共25個
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