Skip to content

Instantly share code, notes, and snippets.

@miracle0k
Created May 4, 2013 05:43
Show Gist options
  • Save miracle0k/7544b90f952ad763d6ca to your computer and use it in GitHub Desktop.
Save miracle0k/7544b90f952ad763d6ca to your computer and use it in GitHub Desktop.
/*
어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.
예를 들면 13195의 소인수는 5, 7, 13, 29 입니다.
600851475143의 소인수 중에서 가장 큰 수를 구하세요.
*/
object p03 {
def run(n : Long) : Long = {
val p = smallestFactor(n);
if (p < n)
run(n / p)
else
return n
} //> run: (n: Long)Long
def smallestFactor(n : Long) : Long = {
val max = Math.sqrt(n.toDouble).toLong
var i = 2l;
while (i < max) {
if (n % i == 0)
return i
i += 1
}
return n
} //> smallestFactor: (n: Long)Long
run(13195) //> res0: Long = 29
run(600851475143l) //> res1: Long = 6857
}
@daclouds
Copy link

daclouds commented May 5, 2013

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment