Skip to content

Instantly share code, notes, and snippets.

@kingori
Created April 21, 2013 04:57
Show Gist options
  • Save kingori/5428538 to your computer and use it in GitHub Desktop.
Save kingori/5428538 to your computer and use it in GitHub Desktop.
project euler 3번
class Euler3 {
/**
* prime 여부
* @param num
* @return
*/
def isPrimeLong(num: Long): Boolean = {
var index = 2L
while (index < num) {
if (num % index == 0) return false
index += 1
}
return true
}
/**
* 주어진 숫자의 소인수 중 특정 숫자 이상의 소인수
* @param num
* @param lastPrimeNum
* @return
*/
def intFraction(num: Long, lastPrimeNum: Long = 2L): List[Long] = {
var startNum = lastPrimeNum
while (startNum <= num) {
if (isPrimeLong(startNum) && num % startNum == 0) {
return startNum :: intFraction(num / startNum, startNum)
}
startNum += 1
}
return List[Long]()
}
def getMaxPrimeFraction(num: Long) = intFraction(num).max
}
object Euler3 extends App {
/**
* 어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.
예를 들면 13195의 소인수는 5, 7, 13, 29 입니다.
600851475143의 소인수 중에서 가장 큰 수를 구하세요.
*/
println(new Euler3().getMaxPrimeFraction(13195L))
println(new Euler3().getMaxPrimeFraction(600851475143L))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment