GESP 5级《初等数论》的考纲要求是什么？

GESP 5级《初等数论》是 CCF 编程能力等级认证（C++）的官方考点，考频★★★、难度★★★。本页严格对照官方考纲逐条拆解要求，配有通俗讲解、必背重点、易错陷阱与考场真题，帮助中小学生零基础系统掌握。

GESP 5级《初等数论》怎么学？有哪些易错点？

学习《初等数论》建议四步：①读「通俗讲解」理解概念；②记「核心必背重点」；③避开「高频易错陷阱」；④用「真题演练」检验。本站为该考点提供 ASCII 图解、例题与历年真题，循序渐进即可通关 GESP 5级。

📌 数论与数学

所属等级：GESP 5级｜难度：★★★ ｜关键词：素数判定、gcd、进制转换、同余

📝 考纲要求

掌握素数判定（试除法）并能写出清晰程序；
理解并编写最大公约数 gcd（辗转相除法）；
掌握进制转换：十进制转 k 进制、k 进制转十进制；
了解同余的基本概念（余数相同），能用于简单判断。

📖 通俗讲解

💡 一句话理解数论就是“整数身上的规律”：能不能分解（素数）、最大能一起分多少（gcd）、换成别的进位制怎么写（进制）、除完剩多少（同余）。

① 素数判定：大于 1，且只能被 1 和自身整除。只需试除到 √n 即可。

🖼️ 图解

gcd 辗转相除：大数除以小数，余数接着当新的除数，
直到余数为 0，最后的除数就是最大公约数。
gcd(48, 18)：
  48 ÷ 18 = 2 ······ 余 12   →  gcd(18, 12)
  18 ÷ 12 = 1 ······ 余 6    →  gcd(12, 6)
  12 ÷ 6  = 2 ······ 余 0    →  gcd(6, 0)
余数为 0，答案 = 6

C++

#include <iostream>
using namespace std;
// 判断 n 是否为素数，是返回 true，否返回 false
bool isPrime(int n) {
    if (n < 2) return false;        // 0、1 不是素数
    for (int i = 2; i * i <= n; i++) { // 只需试到 √n
        if (n % i == 0) return false;  // 找到能整除的因子
    }
    return true;
}
int main() {
    int n; cin >> n;
    if (isPrime(n)) cout << "yes" << endl;
    else cout << "no" << endl;
    return 0;
}

② 最大公约数 gcd（辗转相除法）：gcd(a, b) = gcd(b, a % b)，直到余数为 0。

C++

#include <iostream>
using namespace std;
// 辗转相除法求最大公约数
int gcd(int a, int b) {
    while (b != 0) {        // 余数不为 0 就继续
        int t = a % b;      // 求 a 除以 b 的余数
        a = b;              // b 变成新的被除数
        b = t;              // 余数变成新的除数
    }
    return a;               // 余数为 0 时，a 就是 gcd
}
int main() {
    int x, y; cin >> x >> y;
    cout << gcd(x, y) << endl;
    return 0;
}

③ 进制转换：十进制转 k 进制用“除 k 取余，倒序排列”；k 进制转十进制用“按权展开求和”。

C++

#include <iostream>
using namespace std;
int main() {
    // 十进制 n 转二进制（除 2 取余，倒序）
    int n = 13;
    int ans[40], len = 0;
    while (n > 0) {
        ans[len++] = n % 2;  // 记录余数（最低位在先）
        n = n / 2;           // 继续除以 2
    }
    for (int i = len - 1; i >= 0; i--) { // 倒序输出
        cout << ans[i];
    }
    cout << endl;
    return 0;
}

输出1101

🔵 核心必背重点

✅ 必背

素数判定循环条件写 i * i <= n（防溢出可用 i <= n / i）；
gcd 模板：while(b){ t=a%b; a=b; b=t; } return a;；
十进制转 k 进制：反复 n % k 取余、n / k，最后倒序；
同余：a % m == b % m 表示 a、b 除以 m 余数相同。

🔑

记忆口诀：“素数试到根号 n，gcd 辗转除到 0；进制转换除 k 取余倒着写，同余看余数一不一样。”

🔴 考试拉分难点

⚠️ 难点

边界：素数判定别漏掉 n < 2 返回 false；
lcm 最小公倍数：lcm(a,b) = a / gcd(a,b) * b，先除后乘防溢出；
进制逆转换：字符数字转数值要减 '0' 或减 48。

🟡 高频易错陷阱

🚫 扣分坑点

素数循环写成 i <= n，效率低且易超时；
gcd 形参顺序搞反、少写 b != 0 导致死循环；
进制转换正序输出余数（应为倒序）；
字符 '7' 当数字 7 用，未减 '0'。

🧪 例题演练

例题 1（基础题）：输出 1~n 中的素数个数

题目：输入 n，统计并输出 1 到 n 之间素数的个数。

C++

#include <iostream>
using namespace std;
bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}
int main() {
    int n, cnt = 0;
    cin >> n;
    for (int x = 1; x <= n; x++) {
        if (isPrime(x)) cnt++;  // 是素数就计数
    }
    cout << cnt << endl;
    return 0;
}

输入 / 输出10 4

例题 2（模拟真题）：十六进制转十进制

题目：输入一个长度不超过 8 的十六进制字符串，输出对应的十进制值。

C++

#include <iostream>
#include <string>
using namespace std;
int main() {
    string s;
    cin >> s;
    long long ans = 0;       // 用 long long 防溢出
    for (int i = 0; i < s.size(); i++) {
        int d;
        if (s[i] >= '0' && s[i] <= '9') d = s[i] - '0'; // 数字字符转数值
        else d = s[i] - 'A' + 10;                        // A~F 转 10~15
        ans = ans * 16 + d;  // 按权展开：累加并左移一位
    }
    cout << ans << endl;
    return 0;
}

输入 / 输出1A 26

🚫 错误示范 int ans = 0; ... ans = ans * 16 + d; 当输入较长十六进制（如 FFFFFFFF）时 int 会溢出变成负数，应使用 long long。