0

要求是列出所有与给定数字的 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

4

2 回答 2

0

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

显而易见的是，与

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

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

如果sqrt返回一个双精度值，并且已知浮点被破坏（或者更确切地说并不总是准确......），则可能是这样。因此，我不会对您的测试有时会返回错误结果感到惊讶。

可以做什么：首先对结果进行轮换，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);
}
于 2018-08-09T12:18:49.773 回答
0

当您找到 的除数i时n，您应该删除ifrom的更高次方，以防止在稍后的扫描中找到nof 的多次方：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

  • n 个因子有2 n - 1种可能的组合。
  • 所有可能的素因数和无平方除数都可以收集在相当小的数组中，后者可以排序和打印。

这是一个更快的 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，对于自动存储仍然可以接受。

于 2018-08-09T13:18:42.563 回答