1什么是质数
9 是质数还是合数？为什么？
算法进阶 · 小纸条
选一章打印。双面打印（按长边翻页）后沿虚线剪开，每张卡片正面题目、背面答案。
第 1 页 · 正面（题目）
2判质数·试除
用这个方法判断 7，会试除哪些数？
3判质数·根号n
判断 97 是否为质数，最多试除到几？
4埃氏筛·思路
用埃氏筛处理 2~10，划掉 2 和 3 的倍数后还剩哪些数？
5埃氏筛·代码
外层 i=2 时，内层会标记哪些下标？
6埃氏筛·优化
i=5 时，内层从哪个数开始标记？
7线性筛·思路
12 的最小质因子是几？线性筛里它由谁划掉？
8线性筛·代码
去掉 if(i%pr[j]==0) break; 会怎样？
9唯一分解定理
把 60 写成质因数幂的乘积。
10质因数分解·代码
分解 18，i 走到 3 时会输出什么？
第 1 页 · 背面（答案）
参考答案（家长）：试除 2、3、4、5、6，都不整除，故 7 是质数。
参考答案（家长）：合数，因为 9=3×3，除了 1 和 9 还有约数 3。
参考答案（家长）：剩 2、3、5、7（4/6/8/10 被 2 划掉，9 被 3 划掉）。
参考答案（家长）：√97≈9.8，最多试到 9，只需试 2~9。
参考答案（家长）：从 25 开始（10、15、20 已被 2、3、5 更小质数处理过）。
参考答案（家长）：4、6、8、10……即所有 2 的倍数。
参考答案（家长）：合数会被重复标记，退化成接近埃氏筛，失去线性。
参考答案（家长）：最小质因子是 2；由 2 划掉（i=6、prime=2 时）。
参考答案（家长）：先被 2 除一次输出 2（n 变 9），i=3 时输出两个 3（9→3→1）。
参考答案（家长）：60=2²×3×5。
第 2 页 · 正面（题目）
11分解·剩余质数
分解 14 时，循环结束后 n 等于几？需要输出吗？
12约数成对
24 的约数对有哪些？
13枚举约数
枚举 16 的约数，i 走到几会遇到 i==n/i？
14约数个数
72=2³×3² 有几个约数？
15约数之和
18=2×3² 的约数之和是多少？
16gcd·辗转相除
手算 gcd(24,18) 的每一步。
17gcd·代码
调用 gcd(0,5) 返回几？
18lcm·公式
lcm(4,6) 等于多少？
19gcd性质
用结合性求 gcd(12,18,24)。
20多数 lcm
求 lcm(2,3,4)。
第 2 页 · 背面（答案）
参考答案（家长）：(1,24)(2,12)(3,8)(4,6)，共 8 个约数。
参考答案（家长）：除掉 2 后 n=7，循环内 i*i>7 不再处理，需靠 if(n>1) 输出 7。
参考答案（家长）：(3+1)(2+1)=12 个。
参考答案（家长）：i=4 时 16/4=4，相等，只算一次。
参考答案（家长）：gcd(24,18)=gcd(18,6)=gcd(6,0)=6。
参考答案（家长）：(1+2)(1+3+9)=3×13=39。
参考答案（家长）：gcd=2，4/2×6=12。
参考答案（家长）：5（b=5 非 0，转 gcd(5,0) 返回 5）。
参考答案（家长）：lcm(2,3)=6，再 lcm(6,4)=12。
参考答案（家长）：gcd(12,18)=6，再 gcd(6,24)=6。
第 3 页 · 正面（题目）
21快速幂·直觉
a^8 用折半，需要几次平方？
22快速幂·手算
a^5 对应二进制 101，结果是哪几项相乘？
23快速幂·代码
n=13 时，循环执行几轮后 n 变为 0？
24快速幂·取模
为什么 r 要初始化成 1%p 而不是 1？
25模运算规则
用分配律算 (7+8)%5。
26负数取模
把 -7 对 3 取模修正为非负结果，等于几？
27连乘防溢出
若 p≈10⁹，两个 int 相乘不取模会怎样？
28逆元·直觉
模 7 下，3 的逆元是 5 吗？验证 3×5 mod 7。
29费马小定理
用费马小定理，模 7 下 inv(3) 是 3 的几次方？
30求逆元·代码
模 p 下要算 10/2，应写成什么表达式？
第 3 页 · 背面（答案）
参考答案（家长）：a^4·a^1（5=101₂）。
参考答案（家长）：3 次（a→a²→a⁴→a⁸）。
参考答案（家长）：防止 p=1 时结果应为 0；一般 p>1 时 1%p 就等于 1。
参考答案（家长）：13 有 4 个二进制位，共 4 轮。
参考答案（家长）：((-7%3)+3)%3=((-1)+3)%3=2。
参考答案（家长）：((7%5)+(8%5))%5=(2+3)%5=0。
参考答案（家长）：3×5=15，15 mod 7=1，成立，故 inv(3)=5。
参考答案（家长）：结果可达 10¹⁸，超出 int（约 2×10⁹），会溢出出错。
参考答案（家长）：10*inv(2,p)%p。
参考答案（家长）：3^(7-2)=3^5，算得 243 mod 7=5，与前一致。