Git Bash环境下亲和数查找Shell脚本的优化需求

Great job getting your amicable number script up and running! Let's break down why it's running slow and fix it with some targeted optimizations—these changes will cut down on unnecessary computations and reduce overhead from external commands.

Key Performance Issues in the Original Script #

• Repeated divisor sum calculations: If you input both numbers from an amicable pair (like 220 and 284), the script recalculates their divisor sums twice, wasting time.
• Overhead from external commands: Using awk for square roots and expr for arithmetic calls spawns extra processes, which adds up quickly for large numbers or multiple inputs.
• Unchecked perfect numbers: The current logic treats perfect numbers (where a number equals its divisor sum, e.g., 6) as amicable, which isn't correct—amicable numbers require two distinct values.

Optimized Script #

Here's the revised version with all these fixes:

#!/bin/bash

# Cache to store already calculated divisor sums (avoids redundant work)
declare -A divisor_sum_cache

# Calculate sum of proper divisors (excluding the number itself)
findDivisors() {
    local num=$1
    # Check cache first—return saved value if we've already computed this
    if [[ -n "${divisor_sum_cache[$num]}" ]]; then
        echo "${divisor_sum_cache[$num]}"
        return
    fi

    local sum=1
    # Skip external sqrt call by checking i*i <= num directly
    for ((i=2; i*i <= num; i++)); do
        if (( num % i == 0 )); then
            if (( i == num / i )); then
                ((sum += i))
            else
                ((sum += i + num / i))
            fi
        fi
    done

    # Save result to cache for future use
    divisor_sum_cache[$num]=$sum
    echo "$sum"
}

findAmicableNo() {
    local num=$1
    local s1=$(findDivisors "$num")
    # Skip perfect numbers (s1 == num) since they aren't part of amicable pairs
    if (( s1 == num )); then
        echo "No"
        return
    fi
    local s2=$(findDivisors "$s1")
    if (( s2 == num )); then
        echo "Yes, amicable with $s1"
    else
        echo "No"
    fi
}

# Input handling
echo "Enter the number of inputs:"
read -r n
echo "Enter the numbers:"
declare -A input
for ((i=0; i<n; i++)); do
    read -r n1
    input[$i]=$n1
done

# Process each input
for num in "${input[@]}"; do
    findAmicableNo "$num"
done

What Changed & Why #

• Divisor sum cache: The divisor_sum_cache associative array stores results of previously calculated divisor sums. For example, if you input both 220 and 284, we only compute the sum for 220 once, then reuse that result when processing 284.
• Removed external command overhead:
  • Replaced expr with bash's built-in arithmetic expansion ((...))—this avoids spawning extra processes for every arithmetic check.
  • Eliminated the awk square root call entirely by checking i*i <= num directly in the loop, cutting out another external process.
• Fixed perfect number check: We now skip cases where s1 == num (perfect numbers) since they don't qualify as amicable pairs.
• Improved input safety: Used read -r to handle inputs with backslashes correctly, a small robustness tweak that doesn't hurt performance.

内容的提问来源于stack exchange，提问作者siddhesh nakashe