分解成主要因素

Question

所以我运行遇到了一个我似乎无法解决的问题。我想显示它被提升到的因子和幂（基本上是质因子分解），我在 python 中完成了这个但由于某种原因我不能在 C 中实现它，这就是我想出的与

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

int main()
{
    int i = 2, p, c, n;
    scanf("%d", n);
    while (n > 9)
    {
        p = 0;
        c = 1;
        while (n % i == 0)
        {
            for (int d = 2; d <= i / 2 + 1; d++)
                if (i % d == 0 && i % 2 != 0)
                    c = 0;
            if (c == 1)
            {
                p = p + 1;
                n = n / i;
            }
            if (p != 0)
            {
                printf("%d %d", i, p);
                printf("\n");
            }
            i = i + 1;
        }
    }
    return 0;
}

Answer 1

问题 #1（尽管这不是您的主要问题）是您在 scanf 调用中缺少一个指针：

scanf("%d", n);

那需要

scanf("%d", &n);

（我的编译器立即警告我。不知道为什么你的没有。）

问题 #2 是 while (n > 9) 是完全错误的。我想你想要 while (n > 1).

问题 #3 是 i = i + 1 步骤放错了地方。无论 i 是否是一个因素，你都需要这样做，所以它需要在最外层循环的末尾。

然后问题#4 是以

开头的代码

for (int d = 2; d <= i / 2 + 1; d++)

看起来您正在尝试检查 i 是否为素数，尽管您做得太晚了：您已经在 if 中，您在其中测试 [=19] 是否为素数=] 是 n 的因数。此外，您没有适当的循环来计算 i 是 n.

的因数多少次

不过，事实证明，您实际上 不需要 来测试 i 是否为素数，所以让我们将素数测试步骤放在一边片刻，看看会发生什么。

这是第一个固定版本：

#include <stdio.h>

int main()
{
    int i = 2, p, n;
    scanf("%d", &n);
    while (n > 1)
    {
        if (n % i == 0)           /* if i is a factor */
        {
            p = 0;  
            while (n % i == 0)    /* count how many times i is a factor */
                {
                n /= i;
                p++;
                }
        printf("%d %d\n", i, p);
        }

        i++;
    }
    return 0;
}

这行得通！它会尝试 i 的每个可能值，效率很低，但由于质因数分解的特性，这没关系。它按顺序尝试它们，所以它总是会首先清除所有较低的素数因子，因此 none 的非素数 i 将通过并作为一个因子打印出来。

要完成我猜您想要做的事情，我们必须重新排列代码。基本算法是：对于每个i，如果是素数，看它把运行宁n.

整除多少次

#include <stdio.h>

int main()
{
    int i = 2, p, c, n;
    scanf("%d", &n);
    while (n > 1)
    {
        /* see if i is prime */
        c = 1;
        for (int d = 2; d <= i / 2 + 1; d++)
            if (i % d == 0 && i % 2 != 0)
            {
                c = 0;
                break;
            }

        if (c == 1)                /* if i is prime */
        {
            p = 0;
            while (n % i == 0)     /* count how many times i is a factor */
            {
                p = p + 1;
                n = n / i;
            }

            if (p != 0)
                printf("%d %d\n", i, p);
        }
        i = i + 1;
    }
    return 0;
}

素数测试仍然很粗糙（那行 if (i % d == 0 && i % 2 != 0) 是可疑的），但它似乎有效。不过，我怀疑它仍然很浪费：如果您要生成所有可能的试验除数来分解 n，可能有比运行对每个 i 进行完整的素数测试更好的方法，来自从头开始。

一个流行的快捷方式是 i 运行到 2,3,5,7,9,11,13,...（即 2 加上所有奇数） .基于这个想法，我曾经写过一些使用更复杂的增量序列的代码，因此它最终使用 2、3、5，然后是每个不是 3 或 5 的倍数的奇数。我怀疑（但我还没有测量过）浪费地使用一定数量的非素数试验除数 i 最终可能比肯定地确认每个试验除数都是严格素数更不浪费。

但如果你真的关心效率，你将不得不放弃这种盲目尝试所有试验除数的明显但仍然相当蛮力的技术，并转向更复杂的东西，如 elliptic curve factorization. What we're doing here is trial division, which as Wikipedia notes is "the most laborious but easiest to understand of the integer factorization 算法” .

分解成主要因素

Decomposition into prime factors

c

algorithm

prime-factoring