Project Euler Problem 12 : 500개 이상의 약수를 갖는 가장 작은 삼각수는?

---

Project Euler 문제를 해답을 포스팅합니다.

※ 주의 : 최적화는 할 수 있는 만큼했습니다. 따라서 속도면에서는 많이 부족합니다.

           문제를 푸는데 목표를 두었고 또한 TDD를 최대한 활용하였습니다.

           몇가지 문제의 경우 TDD를 안한 경우도 있습니다.

           혹시, 최적화 또는 속도 증가에 대한 부분을 지적해주실 분은 너무나도 감사합니다.

---

Project Euler Problem 12

1부터 n까지의 자연수를 차례로 더하여 구해진 값을 삼각수라고 합니다.
예를 들어 7번째 삼각수는 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28이 됩니다.
이런 식으로 삼각수를 구해 나가면 다음과 같습니다.

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

이 삼각수들의 약수를 구해봅시다.

 1: 1
 3: 1, 3
 6: 1, 2, 3, 6
10: 1, 2, 5, 10
15: 1, 3, 5, 15
21: 1, 3, 7, 21
28: 1, 2, 4, 7, 14, 28

위에서 보듯이, 5개 이상의 약수를 갖는 첫번째 삼각수는 28입니다.

그러면 500개 이상의 약수를 갖는 가장 작은 삼각수는 얼마입니까?

---

단순히 삼각수 구해고 약수 모두 구해서 카운트하는 방법으로는 미친듯이 돌려야합니다.

약수구하는 공식으로 각 소인수의 지수 + 1을 모두 곱하는 방법이 있으므로 이 공식을 활용하였습니다.

삼각수를 구하는 도중에 소수를 구하여 배열형식으로 저장하는 방법으로 한다면 더 빠르게 구할 수 있을 것 같습니다.

---

Source Code

TestClass Code

public class TestClass { 

    @Test 
    public void testPrimeNumCountCheck() {
        PrimeNumCountChecker checker = new PrimeNumCountChecker();
         
        assertEquals(9l, checker.countPrimeNums(36));
    } 
     
    @Test 
    public void testPrimeNumCheck() {
        PrimeNumCountChecker checker = new PrimeNumCountChecker();
        assertTrue(checker.primeNumCheck(7)); 
        assertTrue(checker.primeNumCheck(11)); 
        assertFalse(checker.primeNumCheck(8)); 
    } 
}

Main Class Code

public class Main { 
    public static void main(String [] args) {
        PrimeNumCountChecker checker = new PrimeNumCountChecker();
         
        long result = 0; 
        long triangularNum = 0;
        long count = 0; 
         
        while(result < 500) { 
            triangularNum += ++count; 
            result = checker.countPrimeNums(triangularNum); 
        } 
         
        System.out.println(result + " " + triangularNum); 
    } 
}

PrimeNumCountChecker Class Code

public class PrimeNumCountChecker {

    public boolean primeNumCheck(long number) {
         
        for(long i=2; i<number/2; i++) {
            if( (number % i) == 0) { 
                return false;
            } 
        } 
        return true; 
    } 

    public long countPrimeNums(long number) {
        long _number = number; 
        long result = 1; 
        long currentPrimeNum = 2;
         
        long primeNumTempCount = 0;
        while(_number != 1) { 
            if( !primeNumCheck(currentPrimeNum) ) { 
                currentPrimeNum++; 
                continue; 
            } 
             
            while( (_number % currentPrimeNum) == 0 ) { 
                primeNumTempCount++; 
                _number /= currentPrimeNum; 
            } 
             
            result *= (primeNumTempCount + 1); 
            currentPrimeNum++; 
            primeNumTempCount=0; 
             
        } 
         
        return result; 
    } 

}