素数又称质数。指在一个大于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！