문제
오세준은 어떤 자연수의 소인수중 최댓값이 K보다 크지 않을때 그 수를 K-세준수라고 부른다.
N보다 작거나 같은 자연수 중에 K-세준수가 총 몇 개인지 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N, 둘째 줄에 K가 주어진다. N은 100,000보다 작거나 같은 자연수이고, K는 100보다 작거나 같은 자연수이다.
출력
첫째 줄에 N보다 작거나 같은 K-세준수가 몇 개인지 출력한다.
해석
1부터 N까지의 수 중에서 2부터 K까지의 수로 나누어 1이 되는 수를 찾으면 된다.
K로 나눌 때 한번 나누는 것이 아니라 나머지가 0이 될 때까지 나눠줘야 한다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#include <iostream>
using namespace std;
void k_sejun(int n, int k) {
int div = 2;
int count = 0;
for (int i = 1; i <= n; i++) {
int tmp = i;
for (int j = 2; j <= k; j++) {
while (tmp % j == 0) {
tmp = tmp / j;
}
}
if (tmp == 1) {
count++;
}
}
cout << count;
}
int main() {
int n, k;
cin >> n >> k;
k_sejun(n, k);
}
|
cs |
Memo
처음에 제출했던 코드는 최악의 경우 10만의 제곱이 넘어가는 연산을 해서 시간초과가 났다.
1초에 약 1억번 정도의 계산이 가능하다는 것을 알게 되었고 어렴풋이 시간복잡도를 계산할 수 있도록 도와준 문제다.