这一篇里的符号如未详细说明则都是整数。
小学时候我们学过加减乘除，我们知道两个整数相加、减、乘得到的结果都是整数，只有除法不一定。那时候我们还没学过小数，我们的解决办法是使用余数。
比如：5/2=2...1，读作五除以2等于2余1。
这里面五是被除数，二是除数，结果中的二是商，省略号后面的一是余数。
我们把它用一般化的式子表示，这也是带余除法定理。
直到大二我也没分清除和除以的关系，导致我第一次看这章的时候云里雾里的。
除和除以都是谓语，代表一个动作，除的主语要是除数，而除以的主语要是被除数。
例如上面的例子，你可以说是五除以二或者二除五，你不能说是二除以五，那样就反了。
假如a除以b的余数为零，也就是说满足a=bc的关系，那么就说明a能被b整除，记作b|a。
如果无法整除记作\(b \nmid a\)
如果一个数只能被1和它本身整除，这个数就是素数，否则就是合数。1既不是素数也不是合数。
2是素数里唯一一个偶数，也是最小的素数。其他偶数都可以被2整除。
我们发现，一个数的最小因数一定是一个素数（除了1）。我们不妨列出几个数看看。
4 - 1,2,4
6 - 1,2,3,6
8 - 1,2,4,8
9 - 1,3,9
12 - 1,2,3,4,6,12
我们可以看到这些因数里除了1和它本身外，最小的都是素数。
证明一下。用反证法吧。
一个合数肯定能拆成若干个素数的乘积。
假如a是和数，一定能找出一个纯素数数列\(m_1...m_n\)乘积为a。
这个证明方式和上面的差不多，不证明了。其实也非常容易想出来。
举个例子
学编程语言的时侯我们大家基本上都写过这个程序。大部分是这样写的：
void get_prime_nums_traditional(){
prime_nums.push_back(2);
for (int i = 3; i <= N; i++) {
int j=2;
for (; j <= i-1; j++) {
if (i % j==0)
break;
}
if (j==i)
prime_nums.push_back(i);
}
}
这个写法没错，而且在教学中是一个很经典的双循环示例。但是我们学了数论之后可就不能这么写了。我们已经探究了素数的很多性质，就应该写出更快速高效的代码。
上面的代码把3～n中的所有数遍历一遍，并且使用一个内循环，再把2到当前数i减1的所有数和i做余数运算，如果在2～i-1中有任何一个数字能整除i，就证明它不是素数。如果没找到整除的数字就是素数。
我们大可不必如此费力。
假设给我们一个数a，我们怎么判断它是否是素数？
我们知道，这个数肯定能写成\(a=bc\)的形式，假设\(b\leq c\)那么就一定有\(b\leq \sqrt{a}\)，因为b大于根号a了c也一定大于根号a，两个大于根号a的数相乘一定大于a。
我们还知道一个合数的最小因数一定是素数，所以我们只需要遍历\([2,\sqrt{a}]\)之间的每一个素数，用这个素数去除a，判断是否能整除，如果能，就证明这个数不是素数，如果都不能整除，就证明这个数是素数。
bool is_prime(int inputNum){
for (int i = 0; i < prime_nums.size() && prime_nums[i] <= sqrt(inputNum); i++){
if (inputNum%prime_nums[i]==0)
return 0;
}
return 1;
}
void get_prime_nums(){
prime_nums.push_back(2);
for (int i = 3; i <= N; i++) {
if (is_prime(i))
prime_nums.push_back(i);
}
}
生成1~100以内的素数，在内循环里添加一个计数器查看内循环执行了多少次。
Traditional : 1133 times
New Algorithm : 181 times
未改进的算法执行了1133次内循环，心算法只执行了181次。
其实对于这个问题，采用时空互换的办法会更好。也就是空间换时间。
因为我们计算机中的数据类型大小是有限制的，比如int类型会有一个能表示的最大值。我们在编写代码时把这个范围内的所有素数都硬编码进程序，这样即可达到O(1)的时间复杂度。
原文：https://www.cnblogs.com/lilpig/p/13760859.html