利用C語言實現(xiàn)高效的因子分解算法

在C語言中，我們可以使用Pollard’s Rho算法來實現(xiàn)一個高效的因子分解算法

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

typedef long long ll;

// 計算兩個數(shù)的最大公約數(shù)
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函數(shù)，用于實現(xiàn)Pollard’s Rho算法。然后，我們定義了一個factorize函數(shù)，用于遞歸地分解輸入的整數(shù)。最后，在main函數(shù)中，我們讀取用戶輸入的整數(shù)，并調(diào)用factorize函數(shù)進(jìn)行因子分解。