纯粹合数与质数子串的算法解析与实现

1. 纯粹合数问题解析与实现

1.1 合数与纯粹合数的定义

合数是指大于1的自然数，除了1和它本身外，还能被其他自然数整除的数。例如4可以被1、2、4整除，所以4是合数；而3只能被1和3整除，所以3不是合数。

纯粹合数则是一个更严格的概念：一个合数，如果去掉它的最高位后剩下的数是0或仍是合数，并且这个性质在逐步去掉最高位的过程中始终保持，直到最后剩下的一位数仍是0或合数，那么这个数就是纯粹合数。

注意：在判断过程中，前置的0会被忽略。例如100去掉最高位1后剩下00，会被视为0。

1.2 纯粹合数的判断算法

判断一个数是否为纯粹合数需要分两步：

1. 首先判断它本身是否是合数
2. 然后递归地判断去掉最高位后的数是否是0或合数

cpp复制bool isHeShu(int n) {
    if (n <= 1) return false;
    for (int i = 2; i <= n/2; i++) {
        if (n % i == 0)
            return true;
    }
    return false;
}

bool isChunCui(int n) {
    while (n > 0) {
        if (!isHeShu(n) && n != 0)
            return false;
        int bei = n / pow(10, to_string(n).length()-1);
        n -= bei * pow(10, to_string(n).length()-1);
    }
    return true;
}

1.3 寻找第n个纯粹合数的实现

我们可以从100开始逐个检查每个数是否是纯粹合数，直到找到足够数量的纯粹合数：

cpp复制vector<int> heshu;
int x = 100;
while (heshu.size() < 100) {
    if (isChunCui(x)) {
        heshu.push_back(x);
    }
    x++;
}

1.4 注意事项与优化建议

1. 边界条件处理：特别注意数字0