如何在C中找到两个给定数字的共同质因数？

Question

我正在尝试解决这个问题：

输入：第一行包含一个整数T，表示您需要解决的案例总数。每个测试用例包含 P 和 Q，由 space 分隔，代表您需要处理的数字。

输出：打印P和Q的最小因数和最大素因数相乘的结果。

约束：1 ≤ ≤ 100 和 2 ≤ , ≤ 1000000

示例输入：2 210 84 6 12
示例输出：

Case #1: 14 
Case #2: 6

说明：我们以第一种情况为例。 210和84这两个数有几个相同的质因数，分别是2、3、7。2是这两个数的最小公质因数，7是它们最大的公质因数。所以，结果一定是2和7的乘积，也就是14。

这是我一直在使用的代码，我试图从给定的数字中找到因子，将因子存储到数组中，然后检查素数，但我觉得这不是正确的算法:(

void factor(int num1) {
    int arrA[100000], a = 0, flag = 1;
    //check factor
    for (int i = 2; i <= num1; i++) {
        if (num1 % i == 0) {
            arrA[a] = i;
            a++;
        }
    }
    // check prime
    for (int i = 0; i < a; i++) {
        for (int j = 2; j < a; j++) {
            if ((arrA[i] % j) == 0) {
                flag = 0;
            }
        }
        if (flag == 1) {
            printf("%d ", arrA[i]);
        }
        flag = 1;
    }
    printf("\n");
}

Answer 1

您的函数无法正确计算质因数，因为它会找到非质因数。对于 num = 6，它会找到 2、3，但也会找到 6。

当您发现 i 除以 num 时，您应该将 num 除以 i，否则增加 i。

然后您可以使 arrA 小得多，因为 int 中质因数的最大数量小于 int 中的位数：31对于 32 位整数和 63 对于 64 位整数就足够了。

一旦你有了 num 的质因数，你应该尝试找到除以另一个数的最小和最大。请注意，第一个和最后一个这样的质数可能相同，如果这些数没有共同的质因数，甚至可能不存在。

请注意，您不需要存储因数：对于 num 的每个质因数，您可以尝试检查它是否能整除另一个数，并保留第一个整除的和最后一个整除的.

这是一个简单的实现：

#include <stdio.h>

int main() {
    int i, n, a, aa, b, p, p1, p2;

    if (scanf("%d", &n) == 1) {
        for (i = 1; i <= n; i++) {
            if (scanf("%d%d", &a, &b) != 2)
                break;
            p1 = p2 = 1;
            aa = a;
            for (p = 2; p * p <= aa; p++) {
                if (aa % p == 0) {
                    /* p is a prime factor of a */
                    if (b % p == 0) {
                        /* p is a common prime factor */
                        p2 = p;
                        if (p1 == 1) {
                            /* p is the smallest common prime factor */
                            p1 = p;
                        }
                    }
                    /* remove p as a factor of aa */
                    do { aa /= p; } while (aa % p == 0);
                }
            }
            if (aa > 1) {
                /* aa is the largest prime factor of a */
                if (b % aa == 0) {
                    /* aa is the largest common prime factor */
                    p2 = aa;
                    if (p1 == 1) {
                        /* aa is also the smallest common prime factor */
                        p1 = aa;
                    }
                }
            }
            /* print the product of the smallest and largest common prime factors */
            /* if a == b and a is a large prime, a * a might overflow int */
            printf("Case #%d: %lld\n", i, (long long)p1 * p2);
        }
    }
    return 0;
}

如何在C中找到两个给定数字的共同质因数？

How to find common prime factors of two given numbers in C?

c

math

primes