本期我们借助一道洛谷的算法题来探讨一下快速判断指定范围内的素数这个问题，原题来自洛谷计算生态[NOIP2012 普及组] 质因数分解，原题如下：
题目描述
已知正整数 n 是两个不同的质数的乘积，试求出两者中较大的那个质数。
输入格式
输入一个正整数 n。
输出格式
输出一个正整数 p，即较大的那个质数。
输入输出样例
输入 #1 输出 #1
21 7
说明/提示
1≤n≤2×1091≤n≤2×109
题目分析
题目给定一个由两个不同质数相乘得到的正整数 n，要求找出其中较大的质数。由于质因数分解具有唯一性，我们可以通过寻找较小质因数来快速推导出答案。
解法详解
在本题中，我们需要掌握的一个重要规律是：除了2和3之外的质数，其位置必定在形式为 6n+1 和6n+5 的位置上(充分不必要)。以下是证明过程：
假设大于等于5的质数必定是6的邻数，考虑6的倍数附近的数：6n+1、6n+2、6n+3、6n+4、6n+5。 其中，
6n+2、6n+3、6n+4均可被分解：
6n+2 = 2(3n+1)
6n+3 = 3(2n+1)
6n+4 = 2(3n+2)
因此，这三个数不可能是质数。剩下的只有6n+1和6n+5可能是质数。
现在我们的任务变成了 判断6n+1和6n+5是否为质数 ，在判断6n+1和6n+5是否为质数时，只需检查这些数是否为6的邻数的倍数即可。
为何无需检查6n+2、6n+3、6n+4的倍数？ 首先，6n+2和6n+4为偶数，不可能是6n+1和6n+5这两个奇数的因数，因此无需检查。 其次，6n+3 = 3(2n+1)，所以6n+3必然是3的倍数。而3的倍数不会出现在6n+1或6n+5的位置上。 因为当n为整数时：
(6n+1)/3 = 2n + 1/3，不可能是整数。
(6n+5)/3 = 2n + 1 + 2/3，也不可能是整数。
所以6n+1和6n+5不可能是6n+3的倍数。因此，6n+1和6n+5只能是6m+1和6m+5的倍数，这也表明质数的两个因数也是6的邻数。
方法一：逆向遍历法（存在缺陷）
实现思路
从 n 向下遍历每个数，判断其是否同时满足：
- 是 n 的因数
- 是质数
优化尝试
基于质数分布的 6k±1 规律进行初步筛选（除2、3外，质数均满足该形式）：
def get_max(nums):
for i in range(nums, 1, -1):
if nums % i == 0 and (i in {2,3} or i%6 in {1,5}):
return i
缺陷说明
此方法存在两处关键问题：
- 未进行完整的质数校验，可能返回合数（如 25 会错误返回5的平方数25）
- 遍历范围过大（需遍历 n~2），时间复杂度为 O(n)
不推荐在实际解题中使用
方法二：质因数分解法（推荐）
数学原理
对于 n = p×q（p < q），当找到最小质因数 p 时，q = n/p 即为所求最大质因数
优化实现
import math
def is_prime(num):
""" 优化的质数判断函数 """
if num < 2:
return False
if num in (2, 3):
return True
if num%2 == 0 or num%3 == 0: # 排除偶数和非6k±1数
return False
# 只需检查6k±1形式的因数，减少工作量
max_div = int(math.sqrt(num)) + 1
for i in range(5, max_div, 6):
if num%i == 0 or num%(i+2) == 0:
return False
return True
def find_max_prime(n):
""" 直接寻找最小质因数 """
if n%2 == 0: # 处理偶数特例
return n//2 if is_prime(n//2) else 2
max_div = int(math.sqrt(n)) + 1
for i in range(3, max_div, 2): # 步长设为2跳过偶数
if n%i == 0:
candidate = n//i
return candidate if is_prime(candidate) else i
return n # n本身是质数的情况（根据题意不会出现）
if __name__ == "__main__":
n = int(input())
print(find_max_prime(n))
复杂度分析
- 时间复杂度：O(√n)
- 空间复杂度：O(1)
优化亮点
- 提前终止机制：找到第一个有效因数即可立即返回结果
- 步长优化：跳过偶数检查，减少循环次数
- 质数判断强化：采用 6k±1 优化策略
- 边界处理：单独处理偶数情况提升效率
算法扩展
对于更复杂的质因数分解场景，可以结合：
- Miller-Rabin 素性测试：处理大整数质数判断
- Pollard’s Rho 算法：高效分解大整数因数
- 预处理质数表：空间换时间策略
注：本题的特殊条件（n为两不同质数乘积）保证了算法的确定性，实际质因数分解问题需考虑更多边界情况。
官网评测
将代码提交到官网进行评测，评测结果如下：
本题成功通过！
如果您在阅读本文的过程中有所收获，或者有任何宝贵的建议和想法，欢迎在评论区留言交流，您的每一个字都将是我前进的动力！在此，博主斗胆向您提出一个小小的请求，如果您觉得本文给您带来了一丝光亮，不妨动动手指，给予一点点鼓励。万水千山总是情，您的打赏，哪怕只是0.1元，也是对博主莫大的支持！（悄悄告诉您，博主正在为服务器众筹中(×﹏×)，您的每一份心意都将助力博主走得更远！）感谢您的慷慨，愿我们的缘分如同这网络世界，绵长不断
评论