写一个大合数因素分解的c语言程序并指出其中Pollard Rho的核心代码和二次筛法的核心代码

以下是一个使用Pollard Rho算法和二次筛法进行大合数因式分解的C语言程序，其中核心代码已标注：

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

#define MAX_PRIME 500000
#define MAX_FACTORS 100

typedef long long ll;

ll prime[MAX_PRIME], factor[MAX_FACTORS];
int cnt;

// Pollard Rho 算法
ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll pollardRho(ll n, ll c) {
    ll x = rand() % (n - 1) + 1;
    ll y = x, i = 1, k = 2;
    while (1) {
        i++;
        x = (x * x % n + c) % n;
        ll d = gcd(y - x, n);
        if (d != 1 && d != n) return d;
        if (y == x) return n;
        if (i == k) { y = x; k <<= 1; }
    }
}

void findFactors(ll n) {
    if (n == 1) return;
    if (MillerRabin(n)) { factor[cnt++] = n; return; }
    ll p = n;
    int c = 1;
    while (p >= n) p = pollardRho(p, rand() % (n - 1) + 1);
    findFactors(p); findFactors(n / p);
}

// 二次筛法
char isPrime[MAX_PRIME];
void init() {
    for (ll i = 2; i < MAX_PRIME; i++) isPrime[i] = 1;
    for (ll i = 2; i * i < MAX_PRIME; i++)
        if (isPrime[i])
            for (ll j = i * i; j < MAX_PRIME; j += i)
                isPrime[j] = 0;
    for (ll i = 2; i < MAX_PRIME; i++)
        if (isPrime[i])
            prime[cnt++] = i;
}

void quadraticSieve(ll n) {
    ll a = sqrt(n); if (a * a == n) { factor[cnt++] = a; factor[cnt++] = a; return; }
    ll m = ceil(sqrt(2.0 * a)) + 1;
    ll *B = (ll*)malloc(m * sizeof(ll));
    char *isComposite = (char*)malloc(m * sizeof(char));
    for (ll i = 0; i < m; i++) B[i] = a + i, isComposite[i] = 0;
    for (int i = 0; i < cnt && prime[i] < m; i++) {
        ll p = prime[i];
        ll k = a % p;
        if (k != 0) k = p - k;
        for (ll j = k; j < m; j += p) {
            ll t = 0;
            while (B[j] % p == 0) { B[j] /= p; t++; }
            isComposite[j] |= (t & 1);
        }
    }
    for (ll i = 0; i < m; i++)
        if (B[i] > 1 && (isSquare(B[i] * n))) { factor[cnt++] = sqrt(B[i] * n); factor[cnt++] = -sqrt(B[i] * n); }
    free(B); free(isComposite);
}

int main() {
    srand(time(NULL));
    init();
    ll n;
    scanf("%lld", &n);
    findFactors(n);
    for (int i = 0; i < cnt; i++) {
        if (factor[i] > 0) quadraticSieve(factor[i]);
        else factor[cnt++] = -1 * factor[i];
    }
    printf("%lld = ", n);
    for (int i = 0; i < cnt; i++) {
        if (i) putchar('*');
        printf("%lld", factor[i]);
    }
    return 0;
}

其中Pollard Rho算法的核心代码为：

ll pollardRho(ll n, ll c) {
    ll x = rand() % (n - 1) + 1;
    ll y = x, i = 1, k = 2;
    while (1) {
        i++;
        x = (x * x % n + c) % n;
        ll d = gcd(y - x, n);
        if (d != 1 && d != n) return d;
        if (y == x) return n;
        if (i == k) { y = x; k <<= 1; }
    }
}

void findFactors(ll n) {
    if (n == 1) return;
    if (MillerRabin(n)) { factor[cnt++] = n; return; }
    ll p = n;
    int c = 1;
    while (p >= n) p = pollardRho(p, rand() % (n - 1) + 1);
    findFactors(p); findFactors(n / p);
}

二次筛法的核心代码为：

void quadraticSieve(ll n) {
    ll a = sqrt(n); if (a * a == n) { factor[cnt++] = a; factor[cnt++] = a; return; }
    ll m = ceil(sqrt(2.0 * a)) + 1;
    ll *B = (ll*)malloc(m * sizeof(ll));
    char *isComposite = (char*)malloc(m * sizeof(char));
    for (ll i = 0; i < m; i++) B[i] = a + i, isComposite[i] = 0;
    for (int i = 0; i < cnt && prime[i] < m; i++) {
        ll p = prime[i];
        ll k = a % p;
        if (k != 0) k = p - k;
        for (ll j = k; j < m; j += p) {
            ll t = 0;
            while (B[j] % p == 0) { B[j] /= p; t++; }
            isComposite[j] |= (t & 1);
        }
    }
    for (ll i = 0; i < m; i++)
        if (B[i] > 1 && (isSquare(B[i] * n))) { factor[cnt++] = sqrt(B[i] * n); factor[cnt++] = -sqrt(B[i] * n); }
    free(B); free(isComposite);
}