오일러 프로젝트 23 (Julia)

어떤 N이 두 초과수의 합으로 표현가능할지를 살펴보는 문제. 유한한 크기의 초과수의 집합이 있다면, 해당 집합의 임의의 원소 e 에 대허서 N - e 가 초과수 집합의 원소인지를 검사해본다. 만약 이 조건을 만족하는 e 가 하나라도 있다면 N은 초과수 2개의 합으로 나타낼 수 있는 수이다.

문제에서 주어진 한계값은 28123이므로 28123 보다 작은 모든 초과수의 집합을 만들고, 24(두 초과수의 합으로 나타낼 수 있는 가장 작은 수)부터 28123까지를 검사해서 초과수의 합으로 나타낼 수 없는 수의 합과 1...23의 합을 더하면 된다.

초과수인지를 검사하는 함수는 이전 문제들에서 사용했던 방식을 그대로 사용하면 되겠다.

function isovernum(n::Int)::Bool
  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^2 == n && (s -= l)
  s > n
end

위 함수를 사용해서 28123 이하의 초과수의 배열을 만들자

L = 28123
ws = filter(isovernum, 1:L) |> collect

메인 풀이는 다음과 같다. ws를 Set으로 만들기 보다는 배열로 만드는 편이 좋은데, n에 대해서 검사할 때 모든 ws의 원소가 아닌 n 보다 작은 값만 확인하면 된다. 크기순으로 정렬돼 있는 ws에서 n보다 작은 범위만 추출하기 위해서는 takewhile() 함수를 사용하면 편리한데, Iterators.takewhile()로 사용한다. (Iterators는 따로 반입할 필요없이 사용할 수 있는 모듈이다.)

@time let L = 28123
  ws = filter(isovernum, 1:L) |> collect
  test(n) = any(x -> (n - x) in ws, Iterators.takewhile(>(n), ws))
    # ws에서 n 보다 작은 값들 중에서 n에서 빼서 다시 초과수 집합에 있는지 검사
    # any(조건, 배열)을 사용하면 배열 원소 중에서 조건식을 만족하는 원소가 1개라도 있으면 true가 된다.
  (sum(1:23) + sum(filter(!test, 24:L))) |> println
end