13282번: Bamboo Blossoms

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

i 보다 작으면서 가장 큰 i의 약수를 pi라고 하자.
그러면 i = m부터 보면서 pi<m인 i에 대해 i-year-bamboos를 심는게 최선이다.

시간복잡도는 $O(L(t+\lg L))$

#include<cstdio>
int m, n, p[8000001];
int main() {
    for (int i = 1; i <= 8e6; i++) for (int j = i * 2; j <= 8e6; j += i) p[j] = i;
    while (scanf("%d%d", &m, &n), m) {
        for (int i = m;; i++) if (!~(n -= p[i] < m)) {
            printf("%d\n", i);
            break;
        }
    }
    return 0;
}