[문제풀이] 약수의 개수가 많은 수

업데이트:

문제 링크 : 약수의 개수가 많은 수

풀이 시간 : 20분 + 10분

1. 문제 풀이

1부터 N까지 약수의 수가 가장 많은 수를 구하는 문제

순열2와 같이 테스트케이스를 돌기 전에 먼저 약수의 개수와 가장 큰 수를 구한다.

1) 1부터 최대값(100001)까지의 약수의 개수를 구한다.

2) 루트 i까지 돌면서 i의 약수의 개수를 구한다.

3) 최대 약수의 개수와 크거나 같으면 i를 저장(같을 경우 i는 증가하기 때문에 현재 i를 저장)

2. 소스 코드

    public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int iter = Integer.parseInt(br.readLine());
		//미리 최대값까지 약수의 개수가 많은 값을 구한다.
		int[] arr = new int[100001];
		//약수의 개수
		int max = 0;
		for (int i = 1; i < 100001; i++) {
			int count = 0;
			//i의 약수의 개수 구하기
			for (int j = 1; j < Math.sqrt(i); j++) {
				if (i % j == 0) {
					count += 2;
				}
			}
			if (Math.sqrt(i) % 1 == 0) {
				count++;
			}
			if (max <= count) {
				//max 보다 크면 변경
				if (max < count) {
					max = count;
				}
				//크거나 같을 경우 순차적으로 진행하기 때문에  arr[i]=i
				arr[i] = i;
			} else {
				arr[i]= arr[i-1];
			}
		}
		for (int i = 1; i <= iter; i++) {
			bw.write("#"+i+" "+arr[Integer.parseInt(br.readLine())]);
			bw.newLine();
		}
		bw.flush();
		bw.close();
	}

3. 후기

약수의 개수를 root를 이용해서 i의 약수의 개수를 구했다.

내 코드보다 빠른 사람의 코드를 보니 에라토스테네스의 체를 활용하여 약수의 개수를 더 빠르게 구했다.

에라토스테네스의 체를 이용해서 단순히 서로소만 구하는 것이 아닌 생각을 하게 되었다.

참고