素数

维基百科，自由的百科全书

素數，又称質數，一個大於1的自然数中，除了1和此整数自身外，沒法被其他自然数整除的数；即是只有兩個正因数（1和自己）的自然数。

比1大但不是素数的数称之为合数又稱合成數，而1和0既非素数也非合数。素数的属性称为素性，素数在数论中有着非常重要的地位。

[编辑] 關於素数

最小的素数是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排斥在素数集合以外。如果1被认为是素数，那么这些严格的阐述就不得不加上一些限制条件了。

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

[编辑] 質数的數目

質数有無限多個。现在已知最古老的检验方法是欧几里德在他的几何原本中提出来的。該检验方法可以简单地总结如下：

假設質數有限, 其中最大的質數為Q。將所有這些有限的質數相乘然後加1，會得到另一個數。此數無法被那些有限質數裡任何一個整除，無論除哪一個，總會餘1，因此該數亦為質數，而且比Q大。這與一開始的假設相矛盾，因此該假設不成立。也就是說，質數並非有限，不存在一個最大的質數。對任何質數來說，永遠可以得到另一個質數比它大，因此質數有無窮多個。

别的数学家也给出了他们自己的证明。歐拉證明了全部素数的倒数和发散到无穷的。恩斯特·库默的证明尤其简洁，Furstenberg用一般拓扑证明。

尽管整个素数是无穷的，仍然有人会问“100000以下有多少个素数?”，“一个随机的100位数多大可能是素数?”。素数定理可以回答此问题。

[编辑] 寻找素数

寻找在给定限度内的素数排列，埃拉托斯特尼筛法是个很好的方法。然而在实际中，我们往往是想知道一个给定数是否是素数，而不是生成一个素数排列。进而，知道答案是很高的概率就是已经很满意的了，用素性测试迅速地检查一个给定数（例如，有几千位数的长度）是否是素数是可能的。典型的方法是随机选取一个数，然后围绕着这个数和可能的素数N检查一些方程式。重複這個過程幾次後，它宣布这个数是明显的合数或者可能是素数。这种方法是不完美的：對某些测试而言，例如費馬測試，不论选取了多少随机数都有可能将一些合数判断成可能的素数，这就引出了另一种数伪素数。而像米勒-拉賓測試，雖然只要選取夠多數字來檢驗方程式，就可以保證其檢驗出的質數性是正確的，但這個保證門檻的數量太過龐大，甚至比試除法所需的還要多，在有限時間內運行起來只能知道答案正確的機率很高，不能保證一定正確。

目前最大的已知素数是2^32582657 − 1（此数字位长度是9,808,358），它是在2006年9月4日由GIMPS发现。这组织也在2005年12月15日发现了目前所知第二大的已知素数2^30402457 − 1（此数字位长度是9,152,052）。

数学家一直努力找寻产生素数的公式，但截至目前为止，并没有一个基本函数或是多项式可以正确产生所有的素数。历史上有许多试验的例子：17世纪初法国数学家梅森(Mersenne)在他的一个著作当中讨论了这样一种我们现在称之为梅森素数的素数，M_p=2^p - 1，本来以为只要p是一个素数，n = 2^p - 1就会是一个素数，这在p = 3，p = 5，p = 7都是正确的，但是p = 11时 就不是素数了。

[编辑] 質數算法

• 欲求出小於x的所有質數……

• 根據質數分布特性可以用

• 6n + 0……偶數（2的倍數）。
• 6n + 1……可能為質數？
• 6n + 2……偶數（2的倍數）。
• 6n + 3……3的倍數。
• 6n + 4……偶數（2的倍數）。
• 6n + 5……可能為質數？

• n為大於0, 小於((x 的平方根) /6)的正整數

• 所以，如果預先排除了 2 與 3 的話……

那只要算 6n + 1 與 6n + 5 是否為質數就好了。 這樣，搜尋範圍立刻少掉原本的2/3, 也比單單排除的偶數還少了1/3。

#include <iostream>
using namespace std;
 
const int LIMIT = 1000000;
 
int main()
{
        bool sieve[LIMIT+1];
        int p, j, p2;
 
        int nLIMIT = LIMIT -6;
        for (int i = 7 ; i <= nLIMIT ; i+=6)
        {
                sieve[i] = true;
                sieve[i+2] = false;
                sieve[i+4] = true;
        }
 
        p = 5;
        while ((j = p*p) <= LIMIT)
        {
                p2 = p << 1;
                while (j <= LIMIT)
                {
                        sieve[j] = false;
                        j += p2;
                }
 
                do
                {
                        p += 2;
                } while (sieve[p] == false);
        }
 
 
        cout << "Prime numbers:\n";
        cout << "2,3,5";
 
        nLIMIT = LIMIT -4;
        for (int i = 7 ; i <= nLIMIT ; i += 2)
        {
                if (sieve[i]) cout << "," << i ;
                i+=4;
                if (sieve[i]) cout << "," << i ;
        }
 
        return 0;
}

[编辑] 检验素数

检查一个正整数N是否为素数，最简单的方法就是试除法，将该数N用小于等于的所有素数去试除，若均无法整除，则N为素数。

2002年，印度人 M. Agrawal 、N. Kayal 以及 N. Saxena 提出了 AKS 質數檢驗演算法，證明了可以在多項式時間內檢驗是否為質數。

[编辑] 未解之谜

• 哥德巴赫猜想：是否每個大於2的雙數均可寫成兩個質數之和？
• 孪生素数猜想：孪生素数就是差为2的素数对，例如11和13。是否存在无穷多的孪生素数？
• 斐波那契数列是否存在无穷多的素数？
• 是否存在无穷多梅森素数？
• 在n²与(n + 1)²之间每隔n就有一个素数？
• 是否存在无穷个形式如n² + 1的素数？
• 黎曼猜想

[编辑] 素数的应用

素数近来被利用在密码学上，所谓的公钥就是将想要传递的信息在编码时加入素数，编码之后传送给收信人，任何人收到此信息后，若没有此收信人所拥有的密钥，则解密的过程中（实为寻找素数的过程），将会因为找素数的过程（分解质因数）过久,使即使取得信息也會無意義。

[编辑] 外部連結

• 素網
• Determinación geométrica de los números primos y perfectos