求满足N=p²+q³为0-9全唯一十位数的素数有序对的程序实现

要解决这个问题，不需要生成一亿以上的素数，核心思路是缩小候选范围，反向推导验证，具体步骤如下：

1. 明确N的范围 #

N是10位无前置零的 pandigital 数（0-9各出现一次），因此：
1023456789 ≤ N ≤ 9876543210

2. 锁定素数q的候选范围 #

q是素数，由N = p² + q³可得：

• 上限：q³ ≤ 9876543210 - 2²（最小素数p=2，p²=4）→ q ≤ ∛9876543210 ≈ 2140
• 下限：q³ ≥ 1023456789 - (√9876543210)² → 简化后q ≥ ∛(1023456789 - 99380²) ≈ 1008，取最小素数1009

只需用埃氏筛生成2140以内的所有素数即可，这个范围极小，完全可行。

3. 锁定素数p的候选范围 #

对每个q，计算q³后，p² = N - q³，因此：

• p的下限：p ≥ ceil(√max(4, 1023456789 - q³))（p最小为素数2）
• p的上限：p ≤ floor(√(9876543210 - q³)) → p最大约为99380

同样用埃氏筛生成10万以内的所有素数，后续直接查表验证即可。

4. 验证pandigital数 #

编写辅助函数判断N是否符合要求：

• 长度必须为10
• 首位不为0
• 包含0-9每个数字恰好一次（用集合或数组统计字符出现次数即可）

代码实现示例 #

def is_pandigital(n):
    s = str(n)
    if len(s) != 10 or s[0] == '0':
        return False
    return set(s) == set('0123456789')

# 埃氏筛生成素数表
def sieve(max_num):
    sieve_list = [True] * (max_num + 1)
    sieve_list[0] = sieve_list[1] = False
    for i in range(2, int(max_num**0.5) + 1):
        if sieve_list[i]:
            sieve_list[i*i : max_num+1 : i] = [False] * len(sieve_list[i*i : max_num+1 : i])
    return [i for i, is_prime in enumerate(sieve_list) if is_prime]

# 预生成候选素数
q_candidates = sieve(2140)
p_candidates = sieve(100000)

count = 0

for q in q_candidates:
    q_cubed = q ** 3
    # 计算p的取值边界
    min_p_sq = 1023456789 - q_cubed
    max_p_sq = 9876543210 - q_cubed
    
    if max_p_sq < 4:
        continue
    
    # 计算p的整数边界
    min_p = max(2, int(min_p_sq**0.5) + (1 if int(min_p_sq**0.5)**2 < min_p_sq else 0))
    max_p = int(max_p_sq**0.5)
    
    if min_p > max_p:
        continue
    
    # 二分查找快速定位p的候选区间
    import bisect
    left_idx = bisect.bisect_left(p_candidates, min_p)
    right_idx = bisect.bisect_right(p_candidates, max_p)
    
    # 遍历验证每个p
    for p in p_candidates[left_idx:right_idx]:
        n = p*p + q_cubed
        if is_pandigital(n):
            count += 1

print(f"符合条件的素数有序对数量：{count}")

核心优势 #

• 完全避开了生成大素数的问题，所有筛素数的操作都在10万以内完成，效率极高
• q的候选仅300多个，每个q对应的p候选数量有限，整体计算量极小
• 用二分查找快速定位p的区间，进一步减少遍历次数

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