利用C语言实现高效的因子分解算法

在C语言中，我们可以使用Pollard’s Rho算法来实现一个高效的因子分解算法

#include<stdio.h>
#include <stdlib.h>

typedef long long ll;

// 计算两个数的最大公约数
ll gcd(ll a, ll b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

// Pollard's Rho算法
ll pollards_rho(ll n) {
    if (n % 2 == 0) return 2;

    ll x = rand() % n;
    ll y = x;
    ll c = rand() % n;
    ll d = 1;

    while (d == 1) {
        x = (x * x + c + n) % n;
        y = (y * y + c + n) % n;
        y = (y * y + c + n) % n;
        d = gcd(abs(x - y), n);
    }

    return d;
}

// 递归分解因子
void factorize(ll n, ll *factors, int *count) {
    if (n == 1) return;

    if (n % 2 == 0) {
        factors[*count] = 2;
        (*count)++;
        factorize(n / 2, factors, count);
    } else {
        ll divisor = pollards_rho(n);
        if (divisor != n) {
            factorize(divisor, factors, count);
            factorize(n / divisor, factors, count);
        } else {
            factors[*count] = n;
            (*count)++;
        }
    }
}

int main() {
    ll n;
    printf("Enter the number to be factorized: ");
    scanf("%lld", &n);

    ll factors[100];
    int count = 0;

    factorize(n, factors, &count);

    printf("Factors of %lld:\n", n);
    for (int i = 0; i< count; i++) {
        printf("%lld ", factors[i]);
    }
    printf("\n");

    return 0;
}

这个程序首先定义了一个pollards_rho函数，用于实现Pollard’s Rho算法。然后，我们定义了一个factorize函数，用于递归地分解输入的整数。最后，在main函数中，我们读取用户输入的整数，并调用factorize函数进行因子分解。