如何高效判断数值是否可表示为两个素数的乘积

方案核心思路 #

我们要判断的数值本质是半素数（即可以表示为两个素数的乘积，两个素数可相同），结合待校验数值最大不超过1e6、总数量1e4的特点，采用预筛最小质因子+单次O(1)校验的方案效率最高。

步骤1：预计算1~1e6的最小质因子数组 #

用埃氏筛变种预生成所有数的最小质因子，仅需一次计算，时间复杂度O(n log log n)，1e6规模下运算开销可以忽略：

• 初始化长度为10^6 + 1的数组min_prime，初始值全部为0
• 从2开始遍历到1e6：
  • 若当前数的min_prime值为0，说明它是素数，将它的min_prime赋值为自身
  • 遍历该素数的所有倍数，若倍数的min_prime未赋值，则赋值为当前素数
    参考Python实现代码：

MAX_NUM = 10 ** 6
min_prime = [0] * (MAX_NUM + 1)
for i in range(2, MAX_NUM + 1):
    if min_prime[i] == 0:
        min_prime[i] = i
        if i * i <= MAX_NUM:
            for j in range(i * i, MAX_NUM + 1, i):
                if min_prime[j] == 0:
                    min_prime[j] = i

步骤2：单数值校验逻辑 #

对于任意待校验数值n，仅需三步即可完成判断，时间复杂度O(1)：

1. 取n的最小质因子p = min_prime[n]
2. 计算商q = n // p
3. 验证q是否为素数：即min_prime[q] == q（素数的最小质因子是其本身）

边界情况处理：若n < 2直接返回不符合要求

示例验证 #

• 校验15：最小质因子p=3，q=5，min_prime[5] == 5，符合要求
• 校验6：最小质因子p=2，q=3，min_prime[3] == 3，符合要求
• 校验8：最小质因子p=2，q=4，min_prime[4] == 2 !=4，不符合要求

批量校验效率 #

预筛完成后，1e4个待校验数的总判断次数仅为1e4次，运算耗时不到1ms，远高于逐个对每个数做素数试除的方案。

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