给两个素数，求第一个素数转变成第二个素数所需最小步骤数。每次转换只能改变一位，且转换的中间数都为素数。
最短路径问题，打出一个素数表，对4位数的各个位置0..9暴搜。
比较郁闷的是sqrt()和pow()中必须要用强制转换才行，不记得以前要这样用啊？？CE了几次。
code:
#include<cstdio> #include<cmath> #include<cstring> using namespace std ; bool prim[ 10000] ; bool vis[ 10000] ; int q[ 1000] ; void getPrim(){ for( int i= 1000; i< 10000; i++){ prim[i] = true ; for( int j= 2; j<=sqrt(( double)i); j++){ // 这里必须要强制为double if(i%j== 0){ prim[i] = false ; break ; } } } } int reset( int x, int i){ int temp[ 4], y = 0 ; for( int j= 0; j< 4; j++){ temp[j] = x % 10 ; x = x / 10 ; } temp[i] = 0 ; for( int j= 0; j< 4; j++) y += temp[j] * pow(( double) 10, j) ; return y ; } int main(){ int t, n, m, flag, h, r, head, temp, ans ; scanf( " %d ", &t) ; getPrim() ; while(t--){ scanf( " %d%d ", &n, &m) ; if(n==m){ printf( " 0\n ") ; continue ; } memset(vis, false, sizeof(vis)) ; flag = 0, ans = 0 ; q[ 0] = n, h = 0, r = 1 ; while(r>h&&!flag){ int k = r - h ; ans ++ ; while(k--){ head = q[h++] ; for( int i= 0; i< 4; i++){ temp = reset(head, i) ; for( int j= 0; j<= 9; j++){ int tem = temp + j * pow(( double) 10, i) ; if(tem==m){ flag = 1 ; break ; } if(!vis[tem]&&prim[tem]){ q[r++] = tem ; vis[tem] = true ; } } } } } printf( " %d\n ", ans) ; } return 0 ;
}