d438 - 10533 - Digit Primes
題目描述
題目要求計算給定區間內 digit prime 的數量。Digit prime 定義為一個質數，且其各位數字之和也是質數。
解題思路
首先，使用埃拉托斯特尼篩法預先計算出 1 到 1000000 之間的質數。然後，對於每個數字，檢查它是否為質數，並且其各位數字之和是否也是質數。如果滿足這兩個條件，則將該數字標記為 digit prime。最後，使用前綴和計算出每個數字之前 digit prime 的數量，以便快速查詢給定區間內的 digit prime 數量。
複雜度分析
- 時間複雜度: O(N log log N + M)，其中 N 是篩選的上限 (1000000)，M 是查詢次數。埃拉托斯特尼篩法的時間複雜度為 O(N log log N)，計算每個數字的各位數字之和以及查詢的時間複雜度為 O(M * log N)。
- 空間複雜度: O(N)，用於儲存質數標記和前綴和。
程式碼
#include <stdio.h>
int p[1000001]={1,1},ans[1000001];
inline int read(){
int a(0);
char c('0');
while(c>='0'){
a=(a<<3)+(a<<1)+c-'0';
c=getchar_unlocked();
}
return a;
}
inline void write(int x) {
if(x==0)
putchar_unlocked('0');
else{
int stk[9],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
}
inline bool dig(int v){
if(p[v])return 0;
int tmp=0;
while(v){
tmp+=v%10;
v/=10;
}
if(p[tmp])return 0;
return 1;
}
int main(){
for(int i=2;i<=1000;++i)
for(int j=i+i;j<=1000000;j+=i)
p[j]=1;
for(int i=1;i<=1000000;++i){
if(dig(i))
ans[i]++;
ans[i]+=ans[i-1];
}
int n,x,y;
n=read();
while(n--){
x=read();
y=read();
write(ans[y]-ans[x-1]);
putchar_unlocked('\n');
}
}