오일러 프로젝트 21 (Julia)

10,000 이하의 모든 친화수를 찾는다. 친화수란 자기 자신을 제외한 약수의 합이 서로 같은 수이다. 참고로 완전수는 자기 자신을 제외한 약수의 합이 자신과 같은 수로, 완전수 자신은 친화수에서 제외되어야 한다.

먼저 자신을 제외한 약수의 합을 구하는 함수를 작성해보자. 대상이 되는 값은 10,000 이하의 값이므로 제곱근 이하의 범위에서 약수를 찾아서 더하면 되겠다.

function divsum(n::Int)::Int
  s = 1
  l = Int(floor(sqrt(n) + 0.5))
  k = 2
  while k <= l
    n % k == 0 && (s += k + div(n, k))
    k += 1
  end
  l * l == n && s -= l
  return s
end

다음은 친화수를 찾는 함수이다. 약수의 합을 구하고, 다시 그 값의 약수의 합이 자신이 되는지를 본다.

function findfnum(n)
  s = divsum(n)
  n != s && divsum(s) == n && return s
  return nothing
end

findfnum()은 친화쌍이 있는 경우 해당 값을, 없는 경우에는 nothing을 리턴한다. 이 값이 nothing이 아닌 경우에 해당 값과 그 친화쌍을 Set에 넣고 합산하면 되겠다. 이미 검사한 수의 친화쌍인 경우 검사하지 않는 것도 도움이 될까 싶은데, 실제로는 별 차이가 없는 것 같다.

@time let s = Set{Int}()
  for x=2:10000
    x in s && continue
    y = fnum(x)
    y !== nothing && push!(s, x)
  end
end