e684 - 00897 - Anagrammatic Primes
題目描述
題目要求對於給定的數字 n，找出大於 n 且具有相同位數的最小 "anagrammatic prime"。 "Anagrammatic prime" 指的是無論如何重新排列其數字，結果仍然是質數的質數。如果找不到這樣的數字，則輸出 0。
解題思路
由於輸入的數字 n 的範圍限制在 10000000 以內，且題目要求找出大於 n 的最小 anagrammatic prime，因此可以預先計算所有小於 10000000 的 anagrammatic prime，並將它們儲存在一個陣列中。然後，對於每個輸入的 n，只需在預先計算的陣列中查找第一個大於 n 的數字即可。
程式碼中，ans 陣列儲存了所有小於 1000 的 anagrammatic primes。對於大於 1000 的輸入，程式碼會迭代 ans 陣列，直到找到大於輸入 n 的第一個元素。如果沒有找到，則輸出 0。
複雜度分析
- 時間複雜度: O(1) - 因為
ans陣列的大小是固定的，查找操作只需要線性掃描這個陣列，但陣列大小有限。 - 空間複雜度: O(1) -
ans陣列的大小是固定的，不隨輸入大小變化。
程式碼
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include <stdio.h>
int ans[22]={2,3,5,7,11,13,17,31,37,71,73,79,97,113,131,199,311,337,373,733,919,991};
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) {
int stk[4],*ptr(&stk[0]);
while(x){*ptr=x%10;x/=10;++ptr;}
while(--ptr>=(&stk[0])){putchar_unlocked(*ptr+'0');}
}
int main(){
int n;
while(n=read()){
if(!n)break;
if(n>990||(n<10&&n>6))
putchar_unlocked('0');
else
for(int *i(&ans[0]);;++i)
if(*i>n){
write(*i);
break;
}
putchar_unlocked('\n');
}
}