[Baekjoon/C++] 1418번 - K-세준수

Baekjoon Online Judge

문제로 이동

 

문제

오세준은 어떤 자연수의 소인수중 최댓값이 K보다 크지 않을때 그 수를 K-세준수라고 부른다.

N보다 작거나 같은 자연수 중에 K-세준수가 총 몇 개인지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N, 둘째 줄에 K가 주어진다. N은 100,000보다 작거나 같은 자연수이고, K는 100보다 작거나 같은 자연수이다.

 

출력

첫째 줄에 N보다 작거나 같은 K-세준수가 몇 개인지 출력한다.

 

---

예제 입력	예제 출력
10 3	7
10 4	7
15 3	8
5 20	5
100000 100	17442

---

풀이

#include <iostream>
using namespace std;

int arr[100001] = { 0, 1 };

int main() {
	int N, K;
	cin >> N >> K;

	for (int i = 2; i <= N; i++) {
		if (arr[i] == 0) {
			for (int j = 2; j <= i; j++) {
				if (j == i) { // 소수일때
					// 소수의 배수에 해당 소수를 입력
					for (int k = i; k <= N; k += i)
						arr[k] = max(arr[k], i);
				}
				if (i % j == 0) break; // 소수가 아닐때
			}
		}
	}

	// K-세준수 세아리기
	int num = 0;
	for (int i = 1; i <= N; i++) {
		if (arr[i] <= K) num++;
	}

	// 출력
	cout << num << endl;

	return 0;
}

사용자가 입력한 N까지의 숫자 중에서 소수를 찾아서 그 배수에 해당하는 칸에 그 소수를 입력했다.

소수 2 발견 > 2, 4, 6, 8 인덱스에 2 저장
소수 3 발견 > 3, 6, 9, 12 인덱스에 3 저장

위의 과정을 통해 각 숫자들의 소인수 중 최댓값을 구했다. 그 뒤 K보다 작은 값을 저장한 인덱스의 개수를 구한 뒤 출력했다.