自建函数

判断质数

质数定义：只能被

1

1 和自身整除的数。

原理：

从 2 开始枚举，一直到

�

−

1

n−1，如果找到一个因数，则该数为合数，否则为质数。

优化：

可以只枚举到

�

n

​

，因为如果能在

�

n

​

前找到一个因子，那么

�

n

​

后面也一定有个因子。

代码

int pr(int n) {

for (int i = 2; i * i <= n; i++) {

if (n % i == 0) {

return 0;

}

}

return n > 1;

}

数位分离

原理：一个数模

10

10 结果一定为该数的个位数，只需要模

10

10 后再除以

10

10 ，最后

�

n 一定变成

0

0。

代码

void sp(int n) {

while (n) {

cout << n % 10;

n /= 10;

}

}

整数反转

原理：将整数数位分离后，再反向拼接成一个整数即可。

代码

int rev(int n) {

int s = 0;

while (n) {

s *= 10;

s += n % 10;

n /= 10;

}

return s;

}

判断整数是否为回文数

原理：求出反转后的数，判断是否相等即可。

代码

int pan(int n) {

return n == rev(n);

}

最大公约数

原理：辗转相除法，

�

a 和

�

b 的最大公约数等于

�

b 和

�

a 的最大公约数。

代码

int gcd(int a, int b) {

return b ? gcd(b, a % b) : a;

}

最小公倍数

int lcm(int a, int b) {

return a / gcd(a, b) * b;

}