第8章 简单算法与数学
本章是 GESP 一级的"算法入门"：进制转换、素数判断、最大公约数/最小公倍数、数位分离，以及把上述技巧组合起来的简单模拟题。
8.1 进制与相互转换
计算机内部用二进制，但人常用十进制，编程中也常用十六进制。要掌握它们之间的转换。
8.1.1 十进制 → 二进制（除 2 取余法）
把十进制数不断除以 2，记下每次的余数，最后把余数倒序排列。
例：把 转成二进制
| 步骤 | 商 | 余数 |
|---|---|---|
| 13 ÷ 2 | 6 | 1 |
| 6 ÷ 2 | 3 | 0 |
| 3 ÷ 2 | 1 | 1 |
| 1 ÷ 2 | 0 | 1 |
余数倒序为 1101，所以 。
// 把十进制 n 转成二进制输出（逆序收集后输出）
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int bits[32], k = 0;
if (n == 0) cout << 0;
while (n > 0)
{
bits[k++] = n % 2; // 取余
n /= 2; // 除 2
}
for (int i = k - 1; i >= 0; i--) // 倒序输出
cout << bits[i];
return 0;
}
8.1.2 二进制 → 十进制（按权展开）
把每一位乘以 的"位权"再相加。例如 ：
8.1.3 八进制与十六进制（简介）
| 进制 | 数字符号 | 前缀 |
|---|---|---|
| 八进制 | 0~7 | 0（C++ 字面量） |
| 十六进制 | 0 | 0x |
- 十六进制中
A=10, B=11, ..., F=15。 - 十进制转十六进制同样用"除 16 取余"，余数 10
15 对应字母 AF。
tip
位十六进制 = 位二进制，所以二进制和十六进制互转非常方便：1101 1010 → DA。考试中常以"填空/选择"形式考查，掌握 的对应即可。
8.2 素数（质数）判断
素数：大于 1，且只能被 1 和自身整除的整数（如 2,3,5,7,11）。
试除法：判断 n 是否为素数，只需用 的整数去试除，若都除不尽则为素数。
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int n;
cin >> n;
bool isPrime = true;
if (n < 2) isPrime = false;
for (int i = 2; i <= sqrt(n); i++)
{
if (n % i == 0) // 找到能整除的因子
{
isPrime = false;
break;
}
}
cout << (isPrime ? "prime" : "not prime") << endl;
return 0;
}
note
只需试到 的原因：若 n 有因子，必有一个 。这把判断次数从 降到 ，效率高很多。
8.3 最大公约数（GCD）与最小公倍数（LCM）
8.3.1 辗转相除法（欧几里得算法）
求 的最大公约数：不断用"较小数"去除"较大数"取余，直到余数为 0，最后的除数就是 GCD。
例：求
- 余
- 余
- 余 → GCD = 6
int gcd(int a, int b)
{
while (b != 0)
{
int t = a % b;
a = b;
b = t;
}
return a; // 余数为 0 时的 a 即最大公约数
}
8.3.2 最小公倍数
int lcm(int a, int b)
{
return a / gcd(a, b) * b; // 先除后乘，避免 a*b 溢出
}
caution
直接写 a * b / gcd 可能整数溢出（尤其 int）。先 a / gcd 再乘 b 更安全。
8.4 数位分离
把整数的每一位拆出来：反复"取个位 + 去掉个位"。
int n = 12345;
while (n > 0)
{
int d = n % 10; // 当前个位
cout << d << " "; // 从个位开始输出：5 4 3 2 1
n /= 10; // 去掉个位
}
tip
数位分离 + 取余判断是很多题的核心：判断回文数、求各位数字之和、统计某位数字出现次数等。
8.5 累加、累乘与最值
| 模式 | 写法 |
|---|---|
| 累加 | sum += x; |
| 累乘 | prod *= x; |
| 最大值 | if (x > maxv) maxv = x; |
| 最小值 | if (x < minv) minv = x; |
// 求 n 的阶乘 n!（累乘）
int n, f = 1;
cin >> n;
for (int i = 1; i <= n; i++)
f *= i;
cout << f << endl;
8.6 简单模拟
"模拟"就是题目怎么说，程序就怎么写，把自然语言步骤翻译成代码。下面用一个综合例子串起"累加 + 数位分离 + 取余"。
【示例】输入一个正整数 n，判断它是否为"水仙花数"（三位数且各位立方和等于自身）。
#include <iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int t = n, sum = 0;
while (t > 0)
{
int d = t % 10; // 分离一位
sum += d * d * d; // 立方累加
t /= 10;
}
cout << (sum == n ? "yes" : "no") << endl;
return 0;
}
【示例】输入 n，输出 中所有素数（综合：循环 + 素数判断）。
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int n;
cin >> n;
for (int x = 2; x <= n; x++)
{
bool ok = true;
for (int i = 2; i <= sqrt(x); i++)
if (x % i == 0) { ok = false; break; }
if (ok) cout << x << " ";
}
return 0;
}
8.7 随堂检测
1. 十进制数 的二进制表示是（ ）。
- A.
1011 - B.
1101 - C.
1110 - D.
1001
查看答案
答案：B。。
2. 判断素数时，试除只需到（ ）即可。
- A.
- B.
- C.
- D.
查看答案
答案：C。若 n 有因子，必有一个不超过 。
3. 已知 ，则 （ ）。
- A. 144
- B. 864
- C. 6
- D. 24
查看答案
答案：A。。