阅读量:0
在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函数进行因子分解。
