테네스의 특별한 소수

1. 소수 만들기 2. 나은 소수 만들기 3. 전처리 미리 해두고 4. 가져다 쓰기 5. 자료구조를 어떻게 만들었는지 6. 10개, 2차원 배열 오케이

#include <stdio.h> bool prime[1000001]; int prefix[1000001][10]; void eratos() { for (int i = 2; i <= 1000000; i++) { prime[i] = true; } for (int i = 2; i <= 1000; i++) { if (prime[i]) { for (int j = i * 2; j <= 1000000; j += i) { prime[j] = false; } } } } void setBetterPrime() { for (int i = 2; i <= 1000000; i++) { if (prime[i]) { int mok; int t = 1; while (mok = i / t) { prefix[i][mok % 10] = 1; t *= 10; } } for (int d = 1; d <= 9; d++) { prefix[i][d] += prefix[i - 1][d]; } } } int main() { freopen("input.txt", "r", stdin); eratos(); setBetterPrime(); int T; scanf("%d", &T); for (int tc = 1; tc <= T; tc++) { int D, A, B; scanf("%d %d %d", &D, &A, &B); printf("#%d %d\n", tc, prefix[B][D] - prefix[A - 1][D]); } return 0; }