C++ 基于蝶数恰好有8个除数的事实的代码

发布于10月30日

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

// Count the number of divisors of a number
int countDivisor(int n)
{
    int divisors = 0;
    for (int i = 1; i <= sqrt(n); i++) {
        if (n % i == 0) {
            if (n / i == i) { // count one divisor for square number
                divisors++;
            } else { // count both divisors for non-square
                divisors += 2;
            }
        }
    }
    return divisors;
}

// Check if number is sphenic
bool isSphenic(int n)
{
    if (n >= 30 && countDivisor(n) == 8) {
        return true;
    }
    return false;
}

int main() 
{
    int n;
    printf("Enter a number: ");
    scanf("%d", &n);
    
    if (isSphenic(n) == true) {
        printf("Sphenic number!");
    } else {
        printf("Not a sphenic number!");
    }
    return 0;
}

这个C代码基于蝶数正好有8个除数这一事实.如果我输入n = 56，则输出将是Sphenic number.我知道这是错误的，但我找不到我的错误.

推荐答案

Sphenic numbers被定义为3个不同素数的乘积.虽然蝶数确实有8个除数，但并不是所有有8个除数的数都是蝶数.

56是2³ * 7，所以它不是一个蝶形数字，但它有8个除数:1、2、4、7、8、14、28和56.

恰好有8个除数的数字分为3个不同的类别:

3个不同素数(楔形数)的乘积:30，42，66，70.
一个素数和另一个素数的立方的乘积:24，40，54，56…
素数的7次方:1282187 78125...

以下是修改后的版本:

bool isSphenic(int n) {
    int factors = 1;
    if (n < 2 * 3 * 5)
        return false;
    for (int p = 2; p <= n / p; p++) {
        if (n % p == 0) {
            factors++;
            n /= p;
            if (n % p == 0)
                return false;
        }
    }
    return factors == 3;
}

正如@Dave所建议的，此代码可以通过两种方式进行改进:

分别处理2个，仅测试奇数(速度提高2x)
最小素因数必须是<；n^1/3，因此搜索素数和2个几乎素数的搜索应该更早停止.(额外快了3x%).

以下是一个更快的版本:

bool isSphenic(int n) {
    int factors = 1;

    if (n % 2 == 0) {
        ++factors;
        n /= 2;
        if (n % 2 == 0)
            return false;
        for (int p = 3; p <= n / p; p += 2) {
            if (n % p == 0) {
                if (++factors > 3)
                    return false;
                n /= p;
                if (n % p == 0)
                    return false;
            }
        }
        return factors == 3;
    }
    for (int p = 3; p * p <= n / p; p += 2) {
        if (n % p == 0) {
            ++factors;
            n /= p;
            if (n % p == 0)
                return false;
            for (p += 2; p <= n / p; p += 2) {
                if (n % p == 0) {
                    if (++factors > 3)
                        return false;
                    n /= p;
                    if (n % p == 0)
                        return false;
                }
            }
            return factors == 3;
        }
    }
    return false;
}