分解为质因数

问题 #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测试是否i为 的因素的地方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 %dn", i, p);
        }

        i++;
    }
    return 0;
}

这有效！它尝试了 的所有可能值i，这非常低效，但由于素数分解的特性，这没关系。它按顺序尝试它们，因此它总是首先清除所有较低的素数因子，因此没有一个非素数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 %dn", 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可能比积极确认每个试除数是严格质数的浪费更少。

但是如果你真的关心效率，你将不得不放弃这种盲目尝试所有试除数的明显但仍然相当暴力的技术，而转向更复杂的东西，比如椭圆曲线分解。我们在这里做的是试验除法，正如维基百科指出的那样，它是“最费力但最容易理解的整数分解算法”。