素数：如果n (n > 1) 是素数, 当且仅当n只有因子1和它本身 ；
应⽤于：
数学: 自然数可由全体素数基底表达
密码学: 构建基于RSA和椭圆曲线的公钥密码学内核
一般方法: 判断n是否被i整除 (i = 2, 3,…, n1/2) ➡ 如果j > n1/2是n的因⼦子, 总能找到i < n1/2, 满⾜足n = i * j
已知的判断素数的检测方法中的次数可达到sqrt(n)，为进一步减少判断次数，引入一种确定性素性测试思想，删减{2, 3,…, n1/2}可能存在合数，减少合数重复判断Eratosthenes筛选。
实验原理：
(1)确定待筛选集合{2, 3,…, n1/2};
(2)基于{2, 3,…, n1/2}的Eratosthenes筛选;（从而开始递增的素数的倍数被标记为0）
(3)筛选后元素与n的整除判断n
代码实现：
#include <iostream> #include <math.h> using namespace std; int main() { int a, i; cin >> a; int b[10000] = { 0 };//初始化为0，用于记录的数组 int c = 0;//count计数 for (int i = 2; i <= sqrt(a); i++) { b[i] = i;//从2到根号a依顺序给数组赋值 } for (int i = 2; i <= sqrt(a); i++) { if (b[i] == 0) continue;//但凡因是倍数被赋0的都跳过 for (int j = i + 1; j <= sqrt(a); j++) { if (b[j] % i == 0 && b[j] != 0) { b[j] = 0;//依次给凡是i的倍数赋值为0 } } c++; b[c] = i;//初始化数组b，记录下符合条件的基数（素数）i } for (i = 1; i <= c; i++) { if (a%b[i] == 0) { cout << a << "不是素数!"; break; } } if (i > c) { cout <<a<< "是素数！"; } }VS2015编译环境运行结果：
