모두의 약수

문제

자연수 N이 입력되면 1부터 N까지의 각 숫자들의 약수의 개수를 출력하는 프로그램을 작성하세요.
만약 N이 8이 입력된다면 1(1개), 2(2개), 3(2개), 4(3개), 5(2개), 6(4개), 7(2개), 8(4개) 와 같이
각 숫자의 약수의 개수가 구해집니다.
출력은 다음과 같이 1부터 차례대로 약수의 개수만 출력하면 됩니다.
1 2 2 3 2 4 2 4 와 같이 출력한다.

입력 예제
8

 

출력 예제
1 2 2 3 2 4 2 4

답

import java.util.Arrays;

public class problem09 {
	
	public static void main(String[] args) {		
		int input = 8;	
		String result = method2(input);
		
		System.out.println(result);
	}
	
	//첫 번째 답: 제한 시간 1초 넘음
	public static String method(int input) {
		String result = "";
		
		for(int i = 1; i<=input; i++) {
			int count = 0;
			
			//input이 3000이면 3000번 돈다.
			for(int j = 1; j<=i; j++) {  
				if(i%j == 0)
					count++;
			}
			
			result = result + count + " ";
		}
		
		return result;
		
	}
	
	//두 번째 답: 제한 시간 1초 안 넘음
	//1~N까지 차례로 배수인 애들만 count 늘려준다.
	public static String method2(int input) {
		int[] count = new int[input];  //0으로 자동으로 초기화.
		
		for(int i = 1; i<=input; i++) {
			
			//j=+i 로 배수만큼 증가시킨다.
            //배수인 애들을 count하는 게 훨씬 빠름. 
			//input이 3000이면 10번만 돈다.
			for(int j = i; j<=input; j+=i) { 
				count[j-1]++;
			}
		}
		
		return Arrays.toString(count);
	}

}