基于斯芬尼克数正好有 8 个除数这一事实的代码-解网

问：

#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 代码基于这样一个事实，即 sphenic 数正好有 8 个除数。如果我输入，输出将是。我知道这是错误的，但我找不到我的错误。n = 56Sphenic number

C 算法

Ruby 有一种用质除数来表示数字的方法。例如，，表示。我之所以提到这一点，只是因为我希望许多其他语言也会有类似的方法或函数，这些方法或函数要么内置在语言中，要么内置在库中。Sphenic 数被定义为等于三个不同素数的乘积的正整数;也就是说，它等于三个素数的乘积，每个素数都提高到一的幂......Prime.prime_division(360) #=> [[2, 3], [3, 2], [5, 1]]360 = (2^3)*(3^2)*(5^1)

0赞 Cary Swoveland 10/30/2023

...在 Ruby 中，假设我们有 .可以看出，三个素数的乘积相等，每个素数的幂为一的幂，我们得出结论，这是一个球数。换句话说，一旦我们得到了这个数字的素数分解——无论使用什么语言——我们就会得出结论，如果它等于三个素数的乘积，每个素数的幂为一。Prime.prime_division(238) #=> [[2, 1], [7, 1], [17, 1]]238238

0赞 Cary Swoveland 10/30/2023

因此，请寻找 Ruby 中的等价物 'Prime.prime_decomposition（n）.transpose.last == [1,1,1]。

1赞 tstanisl 10/30/2023

考虑替换为i <= sqrt(n)i * i <= n

答：

8赞 chqrlie 10/30/2023 #1

闪量被定义为 3 个不同素数的乘积数。虽然 sphenic 数确实正好有 8 个除数，但并非所有具有 8 个除数的数字都是 sphenic 数。

56 是 2³ * 7，所以它不是一个 sphenic 数，但它确实有 8 个除数：1、2、4、7、8、14、28 和 56。

正好有 8 个除数的数字分为 3 个不同的类别：

3 个不同素数（闪光数）的乘积：30、42、66、70......
一个素数和另一个素数的立方的乘积：24、40、54、56......
素数的七次方：128、2187、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 个，只测试奇数（速度快 2 倍）
最小的质因数必须是 < n^1/3，因此应该更早停止对素数和 2 个近素数的搜索。（速度快 3 倍）。

这是一个更快的版本：

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;
}

基于斯芬尼克数正好有 8 个除数这一事实的代码

Code based on the fact that sphenic number has exactly 8 divisors

评论

评论