factor 50

[Bushmills]

factor is not a bash built-in nor a bash plugin. It's a program in its own right, independent of bash, part of gnu coreutils, and is related to bash about as much as, say, a video- or music player is.

busybox provides a factor app too, alas it's much more limited in allowable number range than the coreutils version, which I tend to use as quick poor person's CPU benchmark:

time factor 1234567890123456789012345678901

As this yields two large prime factors, it takes a reasonable (as in measurable) time. Because the number is easy to memorize, and can be shortcut nicely with copy-and-paste, it serves as a nice rough evaluation of CPU performance - depending on machine between about 150ms for notebooks and desktop computers, to 400 to 1000 and above ms for ARM SBC. My WiFi router takes about 4 seconds, comparable to oldish ARM SBCs.

Nevertheless, factor still isn't related to bash.

[mu578]

Good morning, some ideas to write a standalone utility which could emulate GNU factor command when not available.

generate_prime_table() {
    local limit=${1}
    local sieve=( )

    for ((i = 2; i <= limit; i++)); do
        sieve[$i]=1
    done

    for ((i = 2; i <= limit; i++)); do
        if [[ ${sieve[$i]} -eq 1 ]]; then
            for ((j = i * i; j <= limit; j += i)); do
                sieve[$j]=0
            done
        fi
    done

    echo "${!sieve[@]}"
}

# Function to factorize a given product using the prime table
prime_factorize() {
    local product=${1}
    local limit=${2}
    local prime_table=($(generate_prime_table $limit))

    for prime in "${prime_table[@]}"; do
        while ((product % prime == 0)); do
            echo -n "$prime "
            product=$((product / prime))
        done
    done

    if ((product > 1)); then
        echo "$product"
    fi
}

factor() {
    if (( $# != 1 )); then
        echo "Usage: $0 <number>"
        return 1
    fi

    local number=${1}
    local divisor=2

    while (( divisor * divisor <= number )); do
        while (( number % divisor == 0 )); do
            echo -n "$divisor "
            number=$(( number / divisor ))
        done
        ((divisor++))
    done

    if (( number > 1 )); then
        echo "$number"
    fi
}

[Bushmills]

Try your code with the number from my benchmark :)

[mu578]

Alright, it's not ideal. Let's rethink. With bash arithmetic, I can't handle numbers as large as those accepted by the factor command, no bignum support, bound to intmax_t. But second take on a fast factorize placeholder routine (not bad):

function pollards_rho
{
    n=${1}

    function rho
    {
        x=${1} ; y=${1} ; d=1
        function poly
        {
            (( x = (x * x + 1) % n ))
        }

        while [ $d -eq 1 ]; do
            poly $x; poly $y; poly $y
            (( d = (y - x + n) % n ))
            if [ $d -ne 0 ] && [ $d -ne $n ]; then
                return $d
            fi
        done
        return 0
    }
    x=2; y=2; d=1
    while [ $d -eq 1 ]; do
        rho $x
        d=$?
        if [ $d -ne 0 ] && [ $d -ne $n ]; then
            echo "$d "
            pollards_rho $(( n / d ))
            return
        fi
    done
    echo "$n "
}

pollards_rho ${1}

We certainly could tweak more, like splitting strategies, however, one can write a fair placeholder, bash rumbling day. (Prime factors is an addictive topic).