11958번: 행복한 수

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


각 쿼리에 대해
답이 150이하인 경우와 큰 경우로 나뉠 것이다.
시작 지점이 150이하일 경우는 그냥 다 조사한다. 걸리는 시간은 Q*150 정도밖에 안된다.
시작 지점이 150보다 큰 경우, 문제에 제시된 1번 조건을 무시할 수 있다.
고로 k, l이 주어질 때 k개의 연속한 수들 중 150보다 큰 소수가 l개인 경우를 조사하는 문제로 바꿀 수 있다.
1000만 이하의 소수개수는 70만개 이하이므로 주어질 (k,l)쌍에 대한 모든 답을 150*70만 정도에 구할 수 있다.

* 아래 소스는 500만 이하의 소수만 구했다.(대략 40만개)
따로 프로그램을 작성하여 4652354와 이후 149개의 수들은 소수가 아니라는 것을 알 수 있었다.
소수 분포는 점점 드물어지므로 이후에는 답이 존재할 수 없다고 유추할 수 있다.

#include<cstdio>
int ck[5000000] = { 1,1 }, q, k, l, m, p[400000], pcnt, r[151][151];
int main() {
    for (int i = 2; i < 5000000; i++) if (!ck[i]) {
        for (int j = i * 2; j < 5000000; j += i) ck[j] = 1;
        if (i > 150) p[pcnt++] = i;
    }
    for (int i = 0; i < pcnt; i++) {
        for (int j = i; j < pcnt - 1 && p[j] - p[i] < 150; j++)
            for (int l = p[j]; l < p[j + 1] && l < p[i] + 150; l++) r[l - p[i] + 1][j - i + 1] = p[i];
    }
    scanf("%d", &q);
    for (int i = 0; i < q; i++) {
        scanf("%d %d %d", &k, &l, &m);
        int c = 0, j;
        for (j = 1; j < 300; j++) {
            c += (!ck[j] || j <= m) - (j>k&(!ck[j - k] || j - k <= m));
            if (j + 1>k&&c == l) break;
        }
        if (j ^ 300) printf("%d\n", j - k + 1);
        else if (l) printf("%d\n", r[k][l] ? r[k][l] : -1);
        else puts("4652354");
    }
    return 0;
}