프로젝트 오일러 3번 풀이 (Julia)

프로젝트 오일러 3번

어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다. 예를 들면 13195의 소인수는 5, 7, 13, 29입니다.

600851475143의 소인수 중에서 가장 큰 수를 구하세요.

어떤 자연수 N이 다른 자연수 a 로 나누어 떨어진다고 하자. 이 관계를 수식으로 쓰면 $$N = a \times b$$ 이 되는데 이 때, a는 N의 인수가 된다. 그리고 이 때 a가 소수라면 a는 N의 소인수가 된다. 그런데 이 식에서 주목할 점은 b 역시 N을 나눌 수 있는 인수라는 점이다.

다시 자연수 N을 그 소인수들의 곱으로 표현했을 때 \(a \times a \times b \times c\)가 되고 이 때 a < b < c 라면 c가 가장 큰 소인수가 되고, c는 N을 \(a \times a \times b\)로 나눈 몫이 될 것이다.

즉 2부터 시작해서 N을 나눌 수 있을 때 까지 계속 나누고 그 몫에 대해서 3, 4, 5, ... 이런식으로 값을 늘려가면서 계속 나눠본다. 이 과정을 반복하다가 남은 몫이 나누려는 수보다 작아진다면 그 때의 몫을 더 이상 나눌 수 있는 수가 존재하지 않으므로 그 몫이 가장 큰 소인수가 될 것이다.

이 과정을 코드로 표현하면 다음과 같다.

@time let n = 600851475143
    a = 2
    while n > a
        while true
            n % a == 0 && (n = n ÷ a; continue)
            break
        end
        a += 1
    end
    println(n)
end