查找Sphenic数程序无预期输出问题求助

你的代码无法正确识别Sphenic数（三个不同质数的乘积），核心问题出在findSphenic函数的递归逻辑，以及质数判断的细节上，以下是具体问题和修正方案：

原代码的核心问题 #

1. 循环未覆盖当前num本身：
   当递归到最后一步（比如num是质数且当前count=2），原循环从num-1开始遍历，而质数的因数只有1和自身，导致找不到符合条件的j，无法触发count=3的终止条件，直接返回false。

2. 未限制质数唯一性：
   原代码允许重复选择相同质数，会把12=2*2*3这类不符合Sphenic数定义的数误判，因为Sphenic数要求三个不同的质数乘积。

3. 质数判断的精度隐患：
   PrimeNum函数中直接用i <= sqrt(n)，由于sqrt返回double类型，可能存在精度丢失，导致循环提前终止，漏判部分质数。

修正后的完整代码 #

#include <stdio.h>
#include <math.h>
#include <stdbool.h>

bool PrimeNum(int n) {
    if (n <= 1) {
        return false;
    }
    // 将sqrt结果转为整数，避免精度问题
    int sqrt_n = (int)sqrt(n);
    for (int i = 2; i <= sqrt_n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

// 添加prev参数，记录上一次选的质数，确保下一个质数更小（避免重复）
bool findSphenic(int num, int count, int prev) {
    if (num == 1 && count == 3) {
        return true;
    }
    // 提前终止：count达到3或num已分解完但count不足3
    if (count >= 3 || num == 1) {
        return false;
    }

    // 初始调用时prev为0，从num开始遍历；否则从prev-1开始，确保质数不重复
    int start = (prev == 0) ? num : prev - 1;
    for (int j = start; j > 1; j--) {
        if (num % j == 0 && PrimeNum(j)) {
            if (findSphenic(num / j, count + 1, j)) {
                return true;
            }
        }
    }
    return false;
}

void display(int n) {
    for (int k = 1; k <= n; k++) {
        // 初始调用时prev传0
        if (findSphenic(k, 0, 0)) {
            printf("%d\n", k);
        }
    }
}

int main() {
    int num;
    printf("Type in a number: ");
    scanf("%d", &num);
    display(num);
    return 0;
}

测试验证 #

输入45时，程序会正确输出30（235）和42（237），这两个都是1-45范围内的Sphenic数。

内容的提问来源于stack exchange，提问作者Thái Sơn