Amicable_pairs.jl

# Ystäväparit
# Julia-ohjelma Brute Force -menetelmällä
# ensin taulukoidaan summat vektoriksi summa[n]
# Juhani Kaukoranta 20.4.2020

function Amicable_pairs(n)
    # ystäväparit, jotka  < n
    # a ja b ovat ystäväpari (amicable numbers), jos
    # a = kokonaisluvun b tulontekijöiden summa
    # b = kokonaisluvun a tulotekijöiden summa
    # tulontekijat "proper divisors", itse luku ei ole mukana
    # taulukoidaan summat valmiiksi
    divsum = Array{Int64}(undef,n);
    m = div(n,4)  # maksisumma noin n/4
    for j in 2 : m
        divsum[j] = properdivisorsum(j)
    end;
    maxn = maximum(divsum);
    println("n = ",n)
    println("m = ",m)
    println("maksimisumma = ",maxn)
    println("Ystäväparit, jotka pienempiä kuin ", n)
    for i in 2 : m
        j = divsum[i]
        if i < j && i == divsum[j]
            println(i, " ",divsum[i])
        end
    end
end

function properdivisorsum(n)
    n_original = n
    result = 1
    for i in 2 : Int(trunc(sqrt(n)))+1
        curr_sum = 1
        curr_term = 1
        while n % i == 0
            n = div(n,i)
            curr_term = curr_term * i
            curr_sum += curr_term
        end
        result = result * curr_sum
    end
    # This condition is to handle the
    # case when original n is a prime number
    # greater than 2
    if n > 2
        result = result * (1 + n)
    end
    return (result - n_original)
end
time0 = time()
Amicable_pairs(1000000*4)
time1 = time()
println("Aikaa kului ",time1-time0," sekuntia")