Day 4：简单数学问题（素数判断、最大公约数）
数学问题在蓝桥杯中非常重要，尤其是数论基础、数学优化、边界处理等知识。本日的学习目标：
- 素数判断（Prime Number）
- 最大公约数（Greatest Common Divisor，简称 GCD）
- 数学思维转换与优化
一、素数（Prime Number）
1. 什么是素数？
**素数（质数）**是指 大于 1，并且只有 1 和 自身 作为因子的整数。
通俗定义：大于1的自然数，除了1和它本身外，不能被其他数整除。
例子：2（最小的素数）、3、5、7、11等。
非素数（合数）：4（能被2整除）、6（能被2和3整除）。
如何判断素数？
试除法：用2到n-1的数逐个试除，若都除不尽，则为素数。
优化1：只需试除到√n（平方根）。
为什么？ 如果n能被a整除，那么n = a×b，a和b至少有一个≤√n。
优化2：先排除偶数（除了2）。
例如：
2, 3, 5, 7, 11, 13, 17, 19...
反之，合数是指除了 1 和 自身 之外，还可以被其他整数整除的数，例如：
4 = 2 × 2, 6 = 2 × 3, 9 = 3 × 3...
2. 直接枚举法（O(n)）
思路
- 从 2 开始，检查 n 是否能被 2 ~ n-1 中的任何数整除。
- 如果可以被整除，则 n 不是素数。
- 如果没有任何数能整除 n，则 n 是素数。
✅ 代码实现
public class PrimeNumber {
public static boolean isPrime(int n) {
if (n < 2) return false; // 1 不是素数
for (int i = 2; i < n; i++) {
if (n % i == 0) return false; // 有因子，非素数
}
return true;
}
public static void main(String[] args) {
System.out.println(isPrime(7)); // true
System.out.println(isPrime(10)); // false
}
}
✅ 时间复杂度 O(n)，如果 n 很大（例如 10^9），会非常慢 ❌
3. 优化：遍历到 sqrt(n)（O(√n)）
优化思路
- 任何合数 n 必然可以写成两个因子的乘积： n=a×b
- 如果 a > sqrt(n)，则 b < sqrt(n)。
- 也就是说，如果 n 有因子，其中至少有一个 ≤ sqrt(n)。
- 因此，我们只需遍历 2 ~ sqrt(n)，若 n 不能被其中任何数整除，则 n 是素数。
✅ 代码优化
public class OptimizedPrime {
public static boolean isPrime(int n) {
if (n < 2) return false;
if (n == 2) return true; // 2 是唯一的偶数素数
if (n % 2 == 0) return false; // 偶数直接返回 false
int sqrt = (int) Math.sqrt(n);
for (int i = 3; i <= sqrt; i += 2) { // 只检查奇数
if (n % i == 0) return false;
}
return true;
}
public static void main(String[] args) {
System.out.println(isPrime(97)); // true
System.out.println(isPrime(100)); // false
}
}
✅ 时间复杂度 O(√n)，对于 n=10^9 级别问题，能高效处理 ✅
4. 练习题：区间内素数
题目描述
输入两个整数 `a, b`，输出 `[a, b]` 范围内所有的素数。
代码
import java.util.Scanner;
public class PrimeRange {
public static boolean isPrime(int n) {
if (n < 2) return false;
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int a = scanner.nextInt();
int b = scanner.nextInt();
for (int i = a; i <= b; i++) {
if (isPrime(i)) {
System.out.print(i + " ");
}
}
}
}
✅ 时间复杂度 O(n√n)
二、最大公约数（Greatest Common Divisor, GCD）
1. 什么是最大公约数？
通俗定义：两个数都能被整除的最大正整数。
例子：12和18的最大公约数是6。
应用场景：分数化简（如12/18 → 2/3）。
1. 直接枚举法（O(n)）
思路
- 枚举 1 ~ min(a, b)，找到 a 和 b 的最大公因数。
✅ 代码
public class GCD {
public static int gcd(int a, int b) {
int result = 1;
for (int i = 1; i <= Math.min(a, b); i++) {
if (a % i == 0 && b % i == 0) {
result = i;
}
}
return result;
}
public static void main(String[] args) {
System.out.println(gcd(18, 24)); // 输出 6
}
}
✅ 时间复杂度 O(n)，如果 a 和 b 很大，计算会很慢 ❌
2. 欧几里得算法（辗转相除法，O(logn)）
欧几里得算法（辗转相除法）
核心思想：用较大数除以较小数，用余数替换较大数，直到余数为0，最后的非零余数就是GCD。
数学原理：gcd(a, b) = gcd(b, a % b)。
例子：gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) → 6。
数学推导
- 最大公约数定理： GCD(a,b)=GCD(b,aGCD(a, b) = GCD(b, a % b)
- 终止条件： GCD(a,0)=aGCD(a, 0) = a
✅ 代码（递归实现）
public class EuclideanGCD {
public static int gcd(int a, int b) {
return (b == 0) ? a : gcd(b, a % b);
}
public static void main(String[] args) {
System.out.println(gcd(18, 24)); // 输出 6
}
}
✅ 代码（迭代实现，防止递归栈溢出）
public class IterativeGCD {
public static int gcd(int a, int b) {
while (b != 0) {
int temp = a % b;
a = b;
b = temp;
}
return a;
}
public static void main(String[] args) {
System.out.println(gcd(18, 24)); // 输出 6
}
}
✅ 时间复杂度 O(log n)，适用于大数计算 ✅
三、蓝桥杯数学题常考点
| 考点 | 典型题目 | 优化技巧 |
| 素数判断 | 判断素数 | 遍历到 sqrt(n)，跳过偶数 |
| 素数筛选 | 找 1~N 内的素数 | 埃拉托色尼筛法 O(n log log n) |
| 最大公约数 | 求 GCD | 欧几里得算法 O(log n) |
| 最小公倍数 | 求 LCM | LCM(a, b) = (a * b) / GCD(a, b) |
四、蓝桥杯中的常考点和易错点
常考点：
素数判断：试除法和优化到平方根的判断方法。
最大公约数：辗转相除法（欧几里得算法）。
数学模型转换：将实际问题转化为数学模型，通过数学公式或算法求解。
易错点：
边界条件：容易忽略边界条件，如1不是素数。
循环逻辑：在试除法中，循环范围容易写错，应为2到sqrt(num)。
效率问题：在求最大公约数时，容易忘记辗转相除法的优化，导致代码效率低下。
5. 术语解释
素数（Prime Number）：只能被1和自身整除的大于1的自然数。
最大公约数（GCD, Greatest Common Divisor）：两个或多个整数共有约数中最大的一个。
辗转相除法（Euclidean Algorithm）：通过不断求余数来计算最大公约数的方法。
总结
素数判断：通过试除法和优化到平方根的方法，可以高效判断一个数是否为素数。
最大公约数：使用辗转相除法（欧几里得算法）可以快速求解两个数的最大公约数。
数学思维转换：将实际问题转化为数学模型，通过数学公式或算法求解。
蓝桥杯常考点：素数判断、最大公约数、数学模型转换。
易错点：边界条件、循环逻辑、效率问题。
