1418번: K-세준수

https://www.acmicpc.net/problem/1418


$O(n(k+\lg n))$

1~n 수 각각 2~k 사이 소수로 소인수 분해한다.

#include<cstdio>
int n, k, r;
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        int t = i;
        for (int j = 2; j <= k; j++) while (t%j == 0) t /= j;
        r += t == 1;
    }
    printf("%d", r);
    return 0;
}