BAEKJOON / 백준 - JAVA 1418번 K-세준수

2024.04.26 기준 -실버 5

백준, BEAKJOON, BOJ, JAVA, 자바

 

풀이

저는 소인수분해를 통해 문제를 해결했습니다.

주어진 최댓값(max)와 소인수 분해할 최대 인수(k)를 입력받아 해당 범위 냐의 소수 개수를 계산했습니다.

 

for 루프를 통해 2부터 max까지의 모든 수를 검사하며, search() 함수를 호출하여 소수인지 여부를 판단합니다.

소수이면 count를 증가하는 방식입니다.

 

search() 함수에서 for루프를 통해 2부터 최대 소인수 k까지의 모든 수를 나누었습니다.

• 나누어 떨어지고 현재 인수가 k이하일 경우, 나눈 값을 num에 저장하고 i를 1로 초기화시킵니다.
• num이 1이 되면 모든 소인수를 찾은 것으로 true를 반환하고 루프를 종료합니다.
• 인수가 k를 초과하면 루프를 종료합니다.

 

 

코드

public class Main {
	
	static int k;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		int max = Integer.parseInt(br.readLine());
		k = Integer.parseInt(br.readLine());
		int count = 1;
		
        // 소수 개수 세기
		for (int i = 2; i <= max; i++) {
			if (search(i)) {
				count++;
			}
		}
		
		bw.write(Integer.toString(count));
		bw.flush();
		bw.close();
		br.close();
	}
	
	private static boolean search(int n) {
		boolean result = false;
		int num = n;
		
        // 소인수 분해
		for (int i = 2; ; i++) {
			if (num % i == 0 && i <= k) {
				num /= i;
				i = 1;
				
				if (num == 1) {
					result = true;
					break;
				}
			} else if (i > k) {
				break;
			}
		}
		
		return result;
	}
}