[C++백준 1418:세준수]

문제

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

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

입력

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

출력

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

 

해석

1부터 N까지의 수 중에서 2부터 K까지의 수로 나누어 1이 되는 수를 찾으면 된다.

K로 나눌 때 한번 나누는 것이 아니라 나머지가 0이 될 때까지 나눠줘야 한다.

코드

#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);
}

 

Memo

처음에 제출했던 코드는 최악의 경우 10만의 제곱이 넘어가는 연산을 해서 시간초과가 났다.

1초에 약 1억번 정도의 계산이 가능하다는 것을 알게 되었고 어렴풋이 시간복잡도를 계산할 수 있도록 도와준 문제다.