链接：https://vjudge.net/problem/POJ-3126#author=0
思路：一道埃氏筛法 + bfs的题目，因为要测试多个数据所以可以先打印一张五位数内的质数表，然后bfs从起点开始搜索，每次变化一位，然后判断条件并确定是否放入队列，dp数组记录距离（即花费）。
代码：
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 10000;
bool isprime[maxn+1];
int prime[maxn+1];
int dp[maxn+1];
int getnext(int num,int t,int change){
if(t==0)return num/10*10+change;
else if(t==1)return num/100*100+num%10+change*10;
else if(t==2)return num/1000*1000+num%100+change*100;
else return num%1000+change*1000;
}
int main(){
//打表
int p = 0;
for(int i=0;i<=maxn;i++)isprime[i] = true;
isprime[0] = isprime[1] = false;
for(int i=2;i<=maxn;i++){
if(isprime[i]){
prime[p++] = i;
for(int j=2*i;j<=maxn;j+=i){
isprime[j] = false;
}
}
}
int n;
cin>>n;
while(n--){
int a,b;
cin>>a>>b;
memset(dp,0x3f,sizeof(dp));
dp[a] = 0;
//bfs
queue<int> q;
q.push(a);
while(!q.empty()){
int cur = q.front();
q.pop();
for(int i=0;i<4;i++){
for(int j=0;j<10;j++){
if(i==3&&j==0)continue;
int next = getnext(cur,i,j);
if(isprime[next]==false||dp[next]<=dp[cur])continue;
dp[next] = dp[cur] + 1;
q.push(next);
}
}
}
cout<<dp[b]<<endl;
}
return 0;
}
