素數又稱質數。指在一個大于1的自然數中，除了1和此整數自身外，沒法被其他自然數整除的數。換句話說，隻有兩個正因數的自然數即為素數。比1大但不是素數的數稱為合數。1和0既非素數也非合數。合數是由若幹個質數相乘而得到的。是以，質數是合數的基礎，沒有質數就沒有合數。
素數的性質：
1）存在無窮多個素數【反證法】；
2）存在無窮多個形如（4n - 1）的素數【反證法】；
3）任何素數都可以表示為
形式；
3）形如
的素數稱麥什涅數，記做
。設
是一個奇素數，
是一個
的一個素因數，則
有形如：
；
4）
稱費馬數，任意兩個費馬數
，有
，即二者互質；
求解素數的一般方法：
1、傳統解法：最簡單的方法是根據素數的定義來求。對于一個自然數N，用大于1小于N的各個自然數都去除一下N，如果都除不盡，則N為素數，否則N為合數。
2、改進 1）對于一個自然數N，隻要能被一個非1非自身的數整除，它就肯定不是素數，是以不必再用其他的數去除；
2）對于N來說，隻需用小于N的素數去除就可以了；
3）對于N來說，不必用從2到N一1的所有素數去除，隻需用小于等于√N(根号N)的所有素數去除就可以了【反證法】
3、厄拉多塞篩算法：先将2－N的各數放入表中，然後在2的上面畫一個圓圈，然後劃去2的其他倍數；第一個既未畫圈又沒有被劃去的數是3，将它畫圈，再劃去3的其他倍數；現在既未畫圈又沒有被劃去的第一個數 是5，将它畫圈，并劃去5的其他倍數……依次類推，一直到所有小于或等于N的各數都畫了圈或劃去為止。這時，表中畫了圈的以及未劃去的那些數正好就是小于 N的素數。
4、運作時間：
【兩次循環使用“分而治之”思想】
與質數有關的猜想
哥德巴赫猜想（Goldbach Conjecture）大緻可以分為兩個猜想（前者稱“強”或“二重哥德巴赫猜想”後者稱“弱”或“三重哥德巴赫猜想”)：1、每個不小于6的偶數都可以表示為兩個奇素數之和；2、每個不小于9的奇數都可以表示為三個奇質數之和。
黎曼猜想是一個困擾數學界多年的難題，最早由德國數學家波昂哈德·黎曼提出，迄今為止仍未有人給出一個令人完全信服的合理證明。即如何證明“關于質數的方程的所有意義的解都在一條直線上”。
此條質數之規律内的質數月經過整形，“關于質數的方程的所有意義的解都在一條直線上”化為球體質數分布。
1849年，波林那克提出孿生質數猜想（the conjecture of twin primes），即猜測存在無窮多對孿生質數。
猜想中的“孿生質數”是指一對質數，它們之間相差2。例如3和5，5和7，11和13，10016957和10016959等等都是孿生質數。
厄拉多塞篩算法示範如下圖：
基于C++的算法實作：
#include<iostream>
#include<cmath>
//define the N numbers
const int N = 100;
using namespace std;
int main(){
int a[N];
//assign a[i] = i i >= 2
for(int i = 2; i < N; i++){
a[i] = i;
}
//delete 2i, 3i, ... items
for(int i = 2; i <= sqrt(N); i++){
if(0 != a[i]){
for(int j = 2; i * j < N; j++){
a[i * j] = 0;
}
}
}
//print the result
for(int i = 0; i < N; i++){
if(0 != a[i]){
cout << a[i] << " ";
}
}
cout << "done" << endl;
}
practice makes perfect！