[Project Euler] Problem 012

(Java)

public class Problem012 {
    public static void main(String[] args) {
        long beginTime = System.currentTimeMillis();
        System.out.println(run());
        long endTime = System.currentTimeMillis();
        
        System.out.println((endTime - beginTime) + "ms");
    }
    
    public static String run() {
        int n = 0;
        int triNum = 0;
        int max = 0;
        int divs = 0;
        int lim;
        
        while(divs < 500) {
            divs = 2;
            
            if(divs > max) {
                max = divs;
            }
            
            //삼각수 계산
            triNum += ++n;
            
            lim = (int)(Math.sqrt(triNum));
            
            //약수의 개수 계산
            if(triNum%2 != 0) { //삼각수가 홀수일 때
                for(int i = 3; i < lim; i += 2) {
                    if(triNum%i == 0) {
                        divs += 2;
                    }
                }
            } else { //삼각수가 짝수일 때
                for(int i = 2; i < lim; i += 1) {
                    if(triNum%i == 0) {
                        divs += 2;
                    }
                }
            }
        }
        
        return Integer.toString(triNum);
    }
}

정답: 76576500

실행 시간: 0.2초

삼각수 n의 약수의 개수를 셀 때 n이 아니라 √n까지만 반복하면 된다.

예를 들어 55(1~10의 합)의 경우 약수는 1, 5, 11, 55이므로 √55 = 7까지만 반복하면서 약수의 개수를 2개씩 카운팅하면 된다.

int형으로 강제 형 변환 후 거기까지만 반복하면 전체 약수 개수의 절반만큼 세게 되기 때문이다.