[Baekjoon] 1418_K-세준수

Silver V

문제(출처: https://www.acmicpc.net/problem/1418)

---

< K-세준수 >

 

문제 풀이 

 

에라토스테네스의 체를 활용하여 미리 소수를 판별해 둔다. n이하의 값을 각각 소인수를 구한 후 최대 소인수 값이 k보다 작은지 판단한다.

 

 my solution (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class _1418_ { // K-세준수

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

		int n = Integer.parseInt(bf.readLine());
		int k = Integer.parseInt(bf.readLine());

		boolean arr[] = new boolean[100001];
		for (int i = 2; i <= 50001; i++) {
			if (!arr[i]) {
				for (int j = i + i; j < 100001; j += i) {
					arr[j] = true;
				}
			}
		}

		int cnt = 1;
		for (int i = 2; i <= n; i++) {
			if (arr[i]) {
				int temp = 2;
				int num = i;
				int max = -1;
				while (true) {
					if (num % temp == 0) {
						num /= temp;
						max = Math.max(max, temp);
					} else {
						temp++;
					}
					if (temp > num || !arr[num]) {
						max = Math.max(max, num);
						break;
					}
				}
				if (max <= k) {
					cnt += 1;
				}
			} else {
				if (i <= k) {
					cnt += 1;
				}
			}
		}
		System.out.println(cnt);
	}
}

변수)
n, k : 자연수, 최댓값 
arr : 소수 판별
cnt : k-세준수 개수
temp, num, max : 나누는 수, 현재 값, 소인수 최댓값

 

n과 k값을 입력받는다. 에라토스테네스의 체를 사용하여 100000까지 소수를 판별한다. 1은 정답에 포함해야 하므로 cnt를 1로 초기화한다. 2부터 n이하값까지 순환하며 다음 과정을 반복한다.

 

1) 값이 소수가 아니라면

1-1) temp로 나눠준다. temp로 나눠진다면 temp가 소인수 이므로 값을 나누고 소인수 중에서 최댓값을 업데이트한다. 나눠지지 않는다면 temp값을 증가시킨다. 만약 temp가 현재 값보다 크거나 현재 값이 소수라면 더 이상 계산할 필요 없으므로 소인수 중에서 최댓값을 업데이트한 후 종료한다. 소인수 중에서 최댓값이 k이하라면 cnt를 증가시킨다.

2) 값이 소수라면

2-1) 현재 값이 k이하라면 cnt를 증가시킨다.

 

최종 cnt를 출력한다.

---

---