判断x是否能被2到p间数整除的最优复杂度方法探讨

首先，咱们先明确问题核心：我们需要确定是否存在整数i ∈ [2, p]，使得i能整除x（即x % i == 0）。接下来拆解不同方法的优劣，找到最优解：

常规O(p)方法的局限 #

常规遍历2到p的每个数进行取余检查，确实是O(p)的时间复杂度，但当p很大（比如接近x的量级）时，这个方法会变得异常缓慢——比如x=1e9，p=1e9，那要执行1e9次操作，完全不现实。

你提出的O(√x)方法的优化空间 #

你想到的“先找出x的所有因数，再判断是否有因数落在[2,p]区间”的思路，整体复杂度是O(√x)（找因数的时间）加上O(d(x))（遍历因数的时间，d(x)是x的因数个数，远小于√x），确实比O(p)快很多，但这里还有优化的空间：我们不需要找出所有因数，而是可以结合p和√x的大小关系来做更高效的判断。

最优复杂度方法：O(min(p, √x)) #

最优思路是根据p和√x的大小关系，选择最省时间的路径：

步骤1：处理边界情况 #

• 如果p < 2：直接返回false（因为区间[2,p]不存在有效数）
• 如果x < 2：直接返回false（x小于2，无法被任何>=2的数整除）

步骤2：根据p和√x的大小分支处理 #

计算sqrt_x = floor(sqrt(x))（可以用整数二分法找最大的i满足i*i <=x，避免浮点误差）：

1. 当p <= sqrt_x时：
   直接遍历2到p的每个数，检查x % i == 0。只要有一个i满足，就返回true；遍历完都不满足则返回false。

   • 复杂度：O(p)，这比O(√x)更优，因为p <= sqrt_x。

2. 当p > sqrt_x时：
   遍历2到sqrt_x的每个数，检查x % i == 0：

   • 如果找到这样的i，返回true；
   • 如果遍历完都没找到，说明x要么是1，要么是质数。这时候只需判断x >=2且x <=p：如果是，返回true（因为x本身属于[2,p]，能整除自己）；否则返回false。
   • 复杂度：O(√x)，这比O(p)更优，因为sqrt_x < p。

为什么这是最优的？ #

这个方法的时间复杂度是O(min(p, √x))，它取了两种场景下的最小复杂度上界，完美适配了p和x的各种大小组合：

• 当p很小（比如p=100，x=1e18），我们只需要做100次检查，远快于O(√x)的1e9次；
• 当p很大（比如p=1e9，x=1e9），我们只需要做约3e4次检查（√1e9≈31622），远快于O(p)的1e9次。

举几个实际例子：

• x=15，p=4：sqrt_x≈3，p>sqrt_x。遍历2、3，15%3==0，返回true；
• x=7，p=5：sqrt_x≈2，p>sqrt_x。遍历2，7%2≠0，再检查7<=5？否，返回false；
• x=100，p=5：sqrt_x=10，p<=sqrt_x。遍历2-5，100%2==0，返回true；

内容的提问来源于stack exchange，提问作者Abdennacer Lachiheb