(Java) Project Euler 012 - Highly Divisible Triangular Number

// Highly Divisible Triangular Number

// The sequence of triangle numbers is generated by adding the natural numbers.
// So the 7th triangle number would be 1 + 2 + 3 + 4 + 5+ 6 + 7 = 28.
// The first ten terms would be

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

// Let us list the factors of the first seven triangle numbers:

// 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

// We can see that 28 is the first triangle number to have over five divisors.
// What is the value of first triangle number to have over five hundred divisors?

 

 

Question) 

-- 인수가 여러개인 삼각수 (Triangular Number)

-- 삼각수의 수열은 자연수를 1부터 연속적으로 더하여 정의된다.

-- 따라서 7번째 삼각수는 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28이다.

-- 10개의 삼각수는 다음과 같다. : 1, 3, 6, 10, 15, 21, 28, 36, 45, 55 ....

-- 첫 7개의 삼각수에 대해 다음 요소(삼각수에 대한 약수)를 정렬해보자. 

-- 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

-- 삼각수열에서 28(7번째 삼각수)는 5개이상의 약수를 갖는 첫 삼각수라는 것을 알게 되었다.

-- 500개 이상의 인수를 가지는 (삼각수열에서) 첫번째 삼각수는 무엇인가?

 

 

public class ProjectEuler_012 {
    public static void main(String[] args) {
        int n = 1;
        int triangle = 1;

        while (true) {
            int divisors = countDivisors(triangle);

            if (divisors > 500) {
                System.out.println("The first triangular number with 500 more divisors is : " + triangle);
                break;
            }

            n++;
            triangle += n;
        }
    }

    static int countDivisors(int num) {                                     //  1)
        if (num < 1) {
            return 0;
        }

        int count = 0;

        for (int divisor = 1; divisor <= Math.sqrt(num); divisor++) {       //  2)
            if (num % divisor == 0) {                                       //  3)
                count += (divisor == num / divisor) ? 1 : 2;                //  4)
            }
        }

        return count;
    }
}

 

1) 삼각수의 약수 갯수를 세는 메서드 구현함. for문에 1이 들어가면 count가 stack over flow가 되므로, 1의 경우에 대해서 따로 정의하였다.

2) 인수(약수)의 경우 num의 제곱근까지만 반복함.

3) divisor가 num의 약수라면, num/divisor의 근도 num의 약수이므로 count가 2개가 되어야함.

---

삼각수에 대한 정의

삼각수 - 위키백과, 우리 모두의 백과사전