链接：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;
}