trial_division_fast.sf

#!/usr/bin/ruby

# Author: Trizen
# Date: 31 January 2022
# Edit: 21 February 2022
# https://github.com/trizen

# Fast trial division, using an adaptive stepping-ladder algorithm.

func fast_trial_factor(n, F = 2, L = 1e4, R = 1e6) {

    var factors = []
    var P = ::primes(F, L)

    loop {

        ## say "L = #{L} with #{P.len}"

        var g = gcd(n, P.prod)

        # Early stop when n seems to no longer have small factors
        if (g == 1) {
            break
        }

        # Factorize n over primes in P
        P.each {|p|
            if (p `divides` g) {
                var v = n.valuation(p)
                n.remdiv!(p)
                factors << [p, v]
            }
        }

        # Early stop when n has been fully factored or the trial range has been exhausted
        if ((L >= R) || (n == 1)) {
            break
        }

        P = primes(L+1, L<<1)
        L <<= 1
    }

    return (factors, n)
}

#var n = 402641493904540800.primorial_inflation*1e9.random_prime*1e10.random_prime
var n = 12005030196216570240.primorial_inflation*1e9.random_prime*1e10.random_prime

var (f, r) = fast_trial_factor(n)

#var f = n.factor_exp
#var r = 1

say "Found #{f.len} unique prime factors"
say "Remainder = #{r}"

assert_eq(f.prod_2d{|p,e| ipow(p,e) } * r, n)