lightoj1141 - Number Transformation

题目链接：点击打开链接

#include<stdio.h> #include<string.h> #include<algorithm> #include<queue> #define LL long long using namespace std; int pri[1010]; int vis[1010]; void prime() { int i,j; memset(pri,0,sizeof(pri)); for(i=2;i*i<1010;i++) { if(pri[i]==0) { for(j=i*2;j<1010;j+=i) pri[j]=1; } } } void bfs(int a,int b) { int i,u; for(i=a;i<=b;i++) vis[i]=1010; queue<int>q; while(!q.empty()) q.pop(); vis[a]=0; q.push(a); while(!q.empty()) { u=q.front(); q.pop(); if(u==b) return ; for(i=2;i<u;i++) { if(u%i==0&&pri[i]==0) { if((u+i)>b) break; if(vis[u+i]>vis[u]+1)    { vis[u+i]=vis[u]+1; q.push(u+i);    } } } } } int main() { int t,l=1; int a,b; prime(); scanf("%d",&t); while(t--) { scanf("%d%d",&a,&b); bfs(a,b); printf("Case %d: ",l++); if(vis[b]==1010) printf("-1\n"); else printf("%d\n",vis[b]); } return 0; }