如何将整数表示为其质因数的乘积？

Question

//Determine the prime factors of a number
for(i = 2; i <= num; i++) {             //Loop to check the factors.
    while(num % i == 0) {               //While the input is divisible to "i" which is initially 2.
        printf("%d ", i);               //Print the factor.
        num = num / i;                  //Divide the num by "i" which is initially 2 to change the value of num.
        }
    }

我知道这是使用 for 循环求一个数的质因数的方法。但我不知道如何将输出整数表示为其质因数的乘积。例如，INPUT IS: 10 || 输出是：2 x 5 = 10。我们如何做到这一点？ TIA.

Answer 1

你应该：

保存原值。
在每个质因数之间打印运算符 x。
在最后打印原始值。

#include <stdio.h>

int main(void) {
    int num;
    int i;
    int start_num;
    int is_first = 1;
    if(scanf("%d", &num) != 1) return 1;
    start_num = num;                        //Save the original value.

    //Determine the prime factors of a number
    for(i = 2; i <= num; i++) {             //Loop to check the factors.
        while(num % i == 0) {               //While the input is divisible to "i" which is initially 2.
            if(!is_first) printf("x ");     //Print the operator before second and later operands.
            printf("%d ", i);               //Print the factor.
            num = num / i;                  //Divide the num by "i" which is initially 2 to change the value of num.
            is_first = 0;                   //Mark that there is already one or more operand.
        }
    }
    printf("= %d\n", start_num);            //Print the original value.
    return 0;
}

Answer 2

我修改了代码以提供比我之前发布的更强大的东西，同时也稍微更有效率。我再次假设您希望通过 stdin 在以下范围内进行（无符号）32 位输入：[1, 2^32 - 1]

就算法而言，显然搜索因素只需要测试最多 floor(sqrt(num)) 的候选人。还有一些因子具有多重性，例如 (24) => {2, 2, 2, 3}.

此外，分解出(2)后，只需要检验奇个因子。

对于 32 位（无符号）类型，素数将少于 (32) 个。这为用于存储连续质数因子的固定大小数组提供了一个简单的上限。根据所使用的算法，数组中的质数因子按升序排列。

/******************************************************************************/

#include <stdio.h>


int main (void)
{
    /* print a value in [1, 2^32 - 1] as a product of primes: */

    unsigned long int n, u, prime[32];
    int np = 0;

    if (scanf("%lu", & n) != 1 ||
        ((n == 0) || ((n & 0xffffffffUL) != n)))
    {
        fprintf(stderr, "factor < u32 = 1 .. 2^32 - 1 >\n");
        return (1);
    }

    if (n == 1) /* trivial case: */
    {
        fprintf(stdout, "1 = 1\n");
        return (0);
    }

    u = n; /* (u) = working value for (n) */

    for (; (u & 0x1) == 0; u >>= 1) /* while (u) even: */
        prime[np++] = (2);

    while (u > 1)
    {
        unsigned long q, d = 3, c = 0; /* (c)omposite */

        if (np != 0) /* start at previous odd (prime) factor: */
            d = (prime[np - 1] == 2) ? (3) : prime[np - 1];

        for (; (c == 0) && (q = u / d) >= d; )
        {
            if ((c = (q * d == u)) == 0) /* not a factor: */
                d += 2;
        }

        prime[np++] = (d = (c == 0) ? u : d);

        u /= d; /* if (u) is prime, ((u /= d) == 1) (done) */
    }

    for (int i = 0; i < np; i++)
    {
        const char *fmt = (i < np - 1) ? ("%lu x ") : ("%lu = ");
        fprintf(stdout, fmt, prime[i]);
    }

    fprintf(stdout, "%lu\n", n);

    return (0);
}

/******************************************************************************/

Answer 3

您可以输出带有适当标点符号的因素：

// Output the prime factors of a number
void factorize(int num) {
    int n = num;                         // save the initial value of num
    const char *sep = "";                // initial separator is an empty string
    for (int i = 2; i <= num / i; i++) { // stop when num is reduced to a prime
        while (num % i == 0) {           // while the input is divisible to "i"
            num = num / i;               // divide the num by "i" (remove the factor)
            printf("%s%d", sep, i);      // print the separator and the factor.
            sep = " x ";                 // change the separator for any further factors
        }
    }
    if (num > 1 || n <= 1) {
        printf("%s%d", sep, num);          // print the last or single factor.
    }
    printf(" = %d\n", n);                // print the rest of the equation
}

如何将整数表示为其质因数的乘积？

How to express integer as a product of its prime factors?

c

for-loop

integer

primes

prime-factoring