Factorial Mod N - GCD

bginteger.py

import math
import time

def gcd_factorial_efficient(n):
    """Compute GCD(sqrt(n)!, n) efficiently"""
    sqrt_n = int(math.sqrt(n))
    g = n
    
    print(f"Computing GCD({sqrt_n}!, {n})")
    print(f"Processing {sqrt_n} numbers...\n")
    
    start_time = time.time()
    
    for i in range(2, sqrt_n + 1):
        g = math.gcd(g, i)
        
        # Progress indicator every 100,000 iterations
        if i % 100000 == 0:
            print(f"Progress: {i}/{sqrt_n}, current GCD: {g}")
        
        # Early termination if GCD becomes 1
        if g == 1:
            print(f"GCD became 1 at i={i}")
            break
    
    elapsed = time.time() - start_time
    print(f"\nCompleted in {elapsed:.3f} seconds")
    
    return g

# Example with a large integer
n = 123456789012345678901234567890

print("="*60)
print("Example: Computing GCD(sqrt(n)!, n) for large n")
print("="*60)
print(f"n = {n}")
print(f"sqrt(n) ≈ {int(math.sqrt(n))}")
print("="*60 + "\n")

result = gcd_factorial_efficient(n)

print("="*60)
print(f"Final Result: GCD = {result}")
print("="*60)

# Analyze the result
if result > 1:
    print(f"\