在 C 中查找数字的无平方除数

Question

要求列出所有不同于给定数字 1 的除数，这些除数本身不能被完全平方数整除。

到目前为止，这是我的代码：

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

int main() {
    int n, i, temp;
    scanf("%d", &n);

    for (i = 1; i <= n; ++i) {
        if (n % i == 0) {
            temp = sqrt(i);
            if (temp * temp != i)
                printf("%d ", i);
        }
    }
    return 0;
}

如果我输入 20，那么我得到 1 2 4 5 10 20。我已经消除了所有完全平方的数字，即：4.

现在，我 1 2 5 10 20。在这里我不必考虑 1 这意味着我将有 2 5 10 20.

现在，最后，我必须消除所有可以被完全平方数整除的数字，我该怎么做？

示例：20 将被淘汰，因为 4 x 5 = 20 而 4 是一个完美的正方形。

预期输出：2 5 10

Answer 1

你有一个明显的问题和另一个可能的问题。

显而易见的是

    temp = sqrt(i);
    if(temp*temp != i)

你（尝试）测试 i 是否是 一个完全正方形，而不是它是否可以被一个完全正方形整除。这就是为什么你的代码没有消除 20 的原因，它确实可以被 4 整除，但它本身并不是一个完美的正方形。

如果 sqrt returns 是一个双精度值，并且已知浮点数是 broken（或者更准确地说并不总是准确的...），则可能是这样。所以我不会对您的测试有时 returns 错误结果感到惊讶。

可以做什么：首先 round sqrt 的结果而不是（可能）截断它：temp = sqrt(i) + .5; 并测试 i 是否可以被一个完美的平方整除：

if (n%i == 0)
{
    int ok = 1;
    for (temp=2; temp < sqrt(i) + .5; temp++) {
        if (i % (temp * temp) == 0) {
            ok = 0;
            break;
        }
    }
    if (ok) printf("%d ",i);
}

Answer 2

当您找到 n 的除数 i 时，您应该从 n 中删除 i 的更高次幂，以防止 i 的次幂稍后在扫描中被发现：

#include <stdio.h>

int main() {
    int n, i;

    if (scanf("%i", &n) == 1) {
        for (i = 2; i <= n; ++i) {
            if (n % i == 0) {
                printf("%d ", i);
                while (n % (i * i) == 0)
                    n /= i;
            }
        }
        printf("\n");
    }
    return 0;
}

这个算法对于大素数还是很慢的。一种更快的方法是首先在 O(sqrt(N)) 中找到素因子并打印素因子的所有组合，但列表不一定按递增顺序生成。

考虑到这一点：

一个 32 位数最多有 9 个不同的质因数：

29！！ = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29 = 6469693230
有 2ⁿ - 1 种可能的 n 种组合。
所有可能的素因子和无平方除数都可以收集在相当小的数组中，后者可以排序和打印。

这是一个更快的 32 位版本int：

#include <stdio.h>
#include <stdlib.h>

int sort_int(const void *p1, const void *p2) {
    int i1 = *(const int *)p1;
    int i2 = *(const int *)p2;
    return (i1 > i2) - (i1 < i2);
}

int main() {
    int primes[9], divs[1 << 9];
    int i, j, n, p, np, nd;

    if (scanf("%i", &n) == 1) {
        np = 0;
        for (p = 2; p <= n / p; p++) {
            if (n % p == 0) {
                primes[np++] = p;
                while (n % p == 0)
                    n /= p;
            }
        }
        if (n > 1) {
            primes[np++] = n;
        }
        nd = 1 << np;
        for (i = 1; i < nd; i++) {
            divs[i] = 1;
            for (j = 0; j < np; j++) {
                if (i & (1 << j))
                    divs[i] *= primes[j];
            }
        }
        qsort(divs, nd, sizeof(*divs), sort_int);
        for (i = 1; i < nd; i++) {
            printf("%d ", divs[i]);
        }
        printf("\n");
    }
    return 0;
}

64 位 int 可以支持最大数量的质因数 15 而不是 9，自动存储仍然可以接受。

在 C 中查找数字的无平方除数

Finding squarefree divisors of a number in C

c

recursion

question-answering