整除
设 有整数 a,b且 a 不等于 0。
如果存在整数 q，使得 b=aq，那么就说 b 可被 a 整除，记作 a∣b，b 不被 a 整除记作 a∤b。
比如 3∣9的意思是 3能整除 9 ， 而 3∤10是3不能整除 10。
? 给定两个正整数a,b(0<a,b<105), 判断 a 能否整除 b。
if (b % a == 0) {
printf("a 能整除 b");
} else {
printf("a 不能整除 b");
}
取模和取余
C/C++中的运算符 % 其实是取余运算，只是习惯上读作取模。
取余(rem)，遵循尽可能让商向0靠近的原则
取模(mod)，遵循尽可能让商向负无穷靠近的原则
符号相同时，两者不会冲突。
比如，7 ÷ 3 = 2.3，产生了两个商2和3。
7 =3 * 2 + 1 或 7 = 3 * 3 + (-2)。
因此，7 rem 3 = 1，7 mod 3= 1。
符号不同时，两者会产生冲突。
比如，7 ÷ (-3) = -2.3， 产生了两个商 -2 和 -3。
7=(-3) * (-2) + 1 或 7 = (-3) * (-3) + (-2)。
因此，7 rem (-3) = 1， 7 mod (-3) = (-2).
约数(因数)
约数（因数）：若 a∣b，则称 b 是 a 的倍数，a 是 b 的约数(因数)。
? 给定一个正整数 x(0<x<105), 从小到达输出 x 的所有约数(因数)。
for (int i = 1; i <= x; i++) {
if ( x % i == 0) {
printf("%d ", i);
}
}
质数与合数
设整数 p>1。如果 p 除了1和它自身外没有其他约数，那么称 p 为质数（或素数）。
若整数 a≠0,1, 1 且 a 不是质数，则称 a 为合数。
整数的约数(因数)是质数，则该质数称为该整数的质因子。
质数与合数的简单性质：
- 大于 1 的整数 a 是合数，等价于 a 可以表示为整数 d 和 e（1<d,e<a）的乘积。
- 大于 1 的整数 a 一定可以表示为质数的乘积。
- 对于合数 a，一定存在素数 p≤sqrt(a) 使得 p∣a。
- 质数有无穷多个。
? 给定一个正整数 x(0<x<108)x(0<x<108), 判断其是否为质数。
// 函数返回值 0 为合数，1为质数
bool isPrime(int x) {
for (int i = 2; i * i <= x; i++) {
if ( x % i == 0) {
return 0;
}
}
return 1;
}互质(互素)
两个整数互素的定义：若 gcd(a1,a2)=1，则称 a1 和 a2互素。
多个整数互素的定义：若 gcd(a1,…,ak)=1，则称 a1,…,ak 互素。
多个整数互素，不一定两两互素。例如 6、10 和 15 互素，但是任意两个都不互素。