blocks|key|789295|text|看起来像是一个简单的图路径查找问题。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|789296|取所有4位素数作为顶点。用边连接两个，如果我们能从一个到另一个的话。|789297|现在给定两个，你需要在我们刚刚形成的图中找到它们之间的最短路径。一个简单的BFS+(广度优先搜索)就可以做到这一点。|789298|对于有时间限制的编程竞赛，您甚至可以对每个可能的素数对路径进行硬编码，并使运行时间接近于零！|789299|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|J|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|K|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|L|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|M|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|I|$]]

Seems like a straightforward graph path finding problem.

Take all 4 digit primes as the vertices. Connect two with an edge, if we can go from one to the other.

Now given two, you need to find the shortest path between them, in the graph we just formed. A simple BFS (breadth-first-search) should do for that.

For programming contests with time limits, you could even hardcode every possible prime pair path and get close to zero running time!

blocks|key|376865|text|看看“广度优先搜索”。这里还值得注意的是，这个问题可以“从两端”同时解决(从数字X到Y的链可以颠倒，以获得Y到X，您可以利用这一点)。预先计算素数将避免沿途的大量计算。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|376866|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Look into "breadth-first search". Also worth bearing in mind here that the problem can be approached "from both ends" simultaneously (a chain from numbers X to Y can be reversed to get Y to X, and you can exploit this). Precalculating primes will avoid much computation along the way.

blocks|key|4158113|text|建立一个图，其中所有的节点都是4位素数，并且到处都是弧线两个数字有三位数是共同的。从那里，这是一个基本的图遍历，以找到从一个节点到另一个节点的最低成本路径。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4158114|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Build a graph where the nodes are all the 4 digit prime numbers, and there are arcs everywhere two numbers have three digits in common. From there, it's a basic graph traversal to find the lowest-cost path from one node to another.

blocks|key|781954|text|我使用可能的素数测试运行了一个BFS，它在只有4位数的情况下工作得相对较好。同样，由于只有4位数，您可能想要使用更严格的方法来生成所有质数，以进行比较，从而更快地进行质数检查。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|781955|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

I'd run a BFS using probable prime testing, which would work relatively well with only 4 digit numbers. With only 4 digits, also, you may want to use more exacting methods to produce all primes to compare against for faster prime checking.

blocks|key|4158145|text|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4158146|你能给我在邻居列表上声明图形构建的示例代码吗？|blockquote|4158147|4158148|4158149|以下是广度优先搜索的示例代码|4158150|public+static+final+int+MAX+=+10000;
boolean[]+prime+=+new+boolean[MAX];
int[]+dist+=+new+int[MAX];

//get+digit+i+[1+to+4]+in+num
public+int+getDigit(int+num,int+i){
++++return+num+%25+((int)Math.pow(10,+i))+/+((int)+Math.pow(10,+i-1));+
}

//set+digit+i+to+d
public+int+setDigit(int+num,int+i,int+d){
++++return+(num+-+getDigit(num,+i)*(int)Math.pow(10,+i-1))+%2B+d+*+(int)Math.pow(10,i-1);
}

public+int+bfs(int+start,int+end){
++++Queue<Integer>+q+=+new+LinkedList<Integer>();
++++q.add(start);
++++HashSet<Integer>+visited+=+new+HashSet<Integer>();
++++visited.add(start);
++++dist[start]+=+0;
++++int+x,y,d+=+0;
++++while+(q.size()+>+0){
++++++++x+=+q.poll();
++++++++d+=+dist[x];+
++++++++if+(x+==+end)+return+d;

++++++++for+(int+i+=+1;+i+<+5;+i%2B%2B)+{
++++++++++++//digit+number+i
++++++++++++for+(int+j+=+0;+j+<+10;+j%2B%2B)+{
++++++++++++++++//avoid+setting+last+digit
++++++++++++++++if+(j+==+0+&&+i+==+4)+continue;
++++++++++++++++//set+digit+number+i+to+j
++++++++++++++++y+=+setDigit(x,+i,+j);
++++++++++++++++if+(prime[y]+&&+y+!=+x+&&+!visited.contains(y)){
++++++++++++++++++++q.add(y);
++++++++++++++++++++visited.add(y);
++++++++++++++++++++dist[y]+=+d+%2B+1;
++++++++++++++++}
++++++++++++}
++++++++}
++++}
++++return+-1;
}|code-block|syntax|javascript|4158151|entityMap^0|0|0|0|0|0|0^^$0|@$1|2|3|-4|4|5|6|O|7|@]|8|@]|9|$]]|$1|A|3|B|4|C|6|P|7|@]|8|@]|9|$]]|$1|D|3|-4|4|5|6|Q|7|@]|8|@]|9|$]]|$1|E|3|-4|4|5|6|R|7|@]|8|@]|9|$]]|$1|F|3|G|4|5|6|S|7|@]|8|@]|9|$]]|$1|H|3|I|4|J|6|T|7|@]|8|@]|9|$K|L]]|$1|M|3|-4|4|5|6|U|7|@]|8|@]|9|$]]]|N|$]]

<blockquote>
 Could You give me sample code to
 declare graph build on neighbour list?
</blockquote>

here is a sample code for breadth first search

<pre><code>public static final int MAX = 10000;
boolean[] prime = new boolean[MAX];
int[] dist = new int[MAX];

//get digit i [1 to 4] in num
public int getDigit(int num,int i){
 return num % ((int)Math.pow(10, i)) / ((int) Math.pow(10, i-1)); 
}

//set digit i to d
public int setDigit(int num,int i,int d){
 return (num - getDigit(num, i)*(int)Math.pow(10, i-1)) + d * (int)Math.pow(10,i-1);
}

public int bfs(int start,int end){
 Queue&lt;Integer&gt; q = new LinkedList&lt;Integer&gt;();
 q.add(start);
 HashSet&lt;Integer&gt; visited = new HashSet&lt;Integer&gt;();
 visited.add(start);
 dist[start] = 0;
 int x,y,d = 0;
 while (q.size() &gt; 0){
 x = q.poll();
 d = dist[x]; 
 if (x == end) return d;

 for (int i = 1; i &lt; 5; i++) {
 //digit number i
 for (int j = 0; j &lt; 10; j++) {
 //avoid setting last digit
 if (j == 0 &amp;&amp; i == 4) continue;
 //set digit number i to j
 y = setDigit(x, i, j);
 if (prime[y] &amp;&amp; y != x &amp;&amp; !visited.contains(y)){
 q.add(y);
 visited.add(y);
 dist[y] = d + 1;
 }
 }
 }
 }
 return -1;
}
</code></pre>

blocks|key|789367|text|我遇到了一个类似的问题，我必须用最少的步数将一个4位素数1033转换为另一个4位素数3739。我能够解决这个问题，它可能不是很有效，但这里是相同的工作代码。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|789368|以下代码是用Java编写的|789369|import+java.util.*;

public+class+PrimeNumberProblem+{

++++public+static+void+main(String...+args)+{
++++++++System.out.println("Minimum+number+of+steps+required+for+converting+1033+to+3739+are+=+"
++++++++++++++++%2B+getMinSteps(1033,+3739));
++++}

++++public+static+int+getMinSteps(int+a,+int+b)+{
++++++++if+(a+==+b)
++++++++++++return+0;

++++++++List<Integer>+primes+=+new+ArrayList<>();

++++++++//+get+all+the+4+digit+prime+numbers
++++++++primes+=+getPrimeNumbers();

++++++++//+consists+of+graph+with+vertices+as+all+the+prime+numbers
++++++++Graph+graph+=+addNumbersToGraph(primes);

++++++++//+adding+edges+to+the+graph+vertices
++++++++Graph+finalGraph+=+addWeightToGraph(graph);

++++++++//+min+number+of+steps+required
++++++++int+result+=+findShortestRoute(finalGraph.getVertex(a),+finalGraph.getVertex(b));

++++++++return+result;
++++}

++++private+static+int+findShortestRoute(Vertex+source,+Vertex+dest)+{
++++++++if+(source.getVertexValue()+==+dest.getVertexValue())
++++++++++++return+0;

++++++++//+step+1+Initialize+the+queue.+Also+Map+to+store+path
++++++++Queue<Vertex>+visitedQueue+=+new+LinkedList<>();
++++++++Map<Vertex,+Vertex>+currentPrevMap+=+new+HashMap<Vertex,+Vertex>();

++++++++//+step+2+start+from+visiting+S+(starting+node),+and+mark+it+visited,+add+to+queue
++++++++Map<Integer,+Boolean>+visited+=+new+HashMap<Integer,+Boolean>();
++++++++visited.put(source.getVertexValue(),+true);
++++++++visitedQueue.add(source);

++++++++int+level+=+0;
++++++++//+step+3+Repeat+until+queue+is+empty
++++++++while+(!visitedQueue.isEmpty())+{
++++++++++++//+step+4+remove+from+queue
++++++++++++Vertex+current+=+visitedQueue.remove();
++++++++++++if+(current.getVertexValue()+==+dest.getVertexValue())+{
++++++++++++++++printPath(source,+dest,+currentPrevMap);
++++++++++++++++return+level;
++++++++++++}+else+if+(current.getAdjacentVertices().size()+>+0)+{
++++++++++++++++level%2B%2B;
++++++++++++}
++++++++++++//+step+5+add+each+of+the+unvisited+neighbour+and+mark+visited
++++++++++++for+(Vertex+adjacentVertex+:+current.getAdjacentVertices())+{
++++++++++++++++Integer+value+=+adjacentVertex.getVertexValue();
++++++++++++++++if+(value+==+dest.getVertexValue())+{
++++++++++++++++++++currentPrevMap.put(adjacentVertex,+current);
++++++++++++++++++++printPath(source,+dest,+currentPrevMap);
++++++++++++++++++++return+level;
++++++++++++++++}
++++++++++++++++if+(visited.get(value)+==+null)+{
++++++++++++++++++++currentPrevMap.put(adjacentVertex,+current);
++++++++++++++++++++//+mark+visited+and+enqueue+it
++++++++++++++++++++visited.put(value,+true);
++++++++++++++++++++visitedQueue.add(adjacentVertex);
++++++++++++++++}
++++++++++++}
++++++++}
++++++++//+not+found
++++++++System.out.println("Dest+vertex+not+found");
++++++++return+-1;
++++}

++++private+static+void+printPath(Vertex+source,+Vertex+dest,+Map<Vertex,+Vertex>+currentPrevMap)+{
++++++++Vertex+node+=+dest;
++++++++System.out.println("Reverse+Path+from+source:+"+%2B+source.getVertexValue()+%2B+"+to+dest:+"
++++++++++++++++%2B+dest.getVertexValue());
++++++++while+(node+!=+source)+{
++++++++++++System.out.println(node.getVertexValue());
++++++++++++node+=+currentPrevMap.get(node);
++++++++}
++++++++System.out.println(source.getVertexValue());
++++}

++++private+static+Graph+addWeightToGraph(Graph+graph)+{
++++++++List<Vertex>+vertices+=+graph.getAllVertices();
++++++++for+(Vertex+i+:+vertices)+{
++++++++++++for+(Vertex+j+:+vertices)+{
++++++++++++++++if+(i.equals(j))
++++++++++++++++++++continue;

++++++++++++++++if+(distance(i,+j)+==+1)+{
++++++++++++++++++++i.getAdjacentVertices().add(j);
++++++++++++++++++++//+i.addEdge(new+Edge(i,+j,+1));
++++++++++++++++}
++++++++++++}
++++++++}
++++++++return+graph;
++++}

++++private+static+int+distance(Vertex+source,+Vertex+dest)+{
++++++++if+(source.getVertexValue()+==+dest.getVertexValue())+{
++++++++++++return+0;
++++++++}

++++++++char[]+numA+=+extractIntegers(source.getVertexValue());
++++++++char[]+numB+=+extractIntegers(dest.getVertexValue());

++++++++int+len1+=+numA.length;

++++++++int+tracker+=+0;

++++++++for+(int+i+=+0;+i+<+len1;+i%2B%2B)+{

++++++++++++if+(numA[i]+!=+numB[i])+{
++++++++++++++++numA[i]+=+numB[i];
++++++++++++++++tracker%2B%2B;
++++++++++++++++String+sA+=+String.copyValueOf(numA);
++++++++++++++++String+sB+=+String.copyValueOf(numB);
++++++++++++++++//+if+we+have+reached+destination
++++++++++++++++if+(Integer.parseInt(sA)+==+Integer.parseInt(sB))+{
++++++++++++++++++++return+tracker;
++++++++++++++++}
++++++++++++}

++++++++}
++++++++return+tracker;
++++}

++++private+static+char[]+extractIntegers(int+i)+{
++++++++char[]+arr+=+Integer.toString(i).toCharArray();
++++++++return+arr;
++++}

++++private+static+Graph+addNumbersToGraph(List<Integer>+primes)+{
++++++++Graph+g+=+new+Graph();
++++++++for+(Integer+prime+:+primes)+{
++++++++++++g.addVertex(new+Vertex(prime));
++++++++}
++++++++return+g;
++++}

++++private+static+List<Integer>+getPrimeNumbers()+{
++++++++List<Integer>+fourDigitPrimes+=+new+ArrayList<>();
++++++++fourDigitPrimes.add(1033);
++++++++fourDigitPrimes.add(1733);
++++++++fourDigitPrimes.add(3733);
++++++++fourDigitPrimes.add(3739);

++++++++//+for+(int+i+=+1000;+i+<+9999;+i%2B%2B)+{
++++++++//+if+(isPrime(i))
++++++++//+fourDigitPrimes.add(i);
++++++++//+}

++++++++return+fourDigitPrimes;
++++}

++++private+static+boolean+isPrime(int+i)+{

++++++++for+(int+k+=+2;+k+<+Math.sqrt(i);+k%2B%2B)+{
++++++++++++if+(i+%25+k+==+0)
++++++++++++++++return+false;
++++++++}

++++++++return+true;
++++}
}


class+Graph+{
++++public+List<Vertex>+vertexList+=+new+ArrayList<Vertex>();

++++public+void+addVertex(Vertex+V)+{
++++++++vertexList.add(V);
++++}


++++public+List+getAllAdjacentNodes(Vertex+V)+{
++++++++return+V.getAdjacentVertices();
++++}

++++public+List+getAllVertices()+{
++++++++return+vertexList;
++++}

++++public+Vertex+getVertex(int+val)+{
++++++++Iterator<Vertex>+keys+=+vertexList.iterator();
++++++++while+(keys.hasNext())+{
++++++++++++Vertex+v+=+keys.next();
++++++++++++if+(v.getVertexValue()+==+val)
++++++++++++++++return+v;
++++++++}
++++++++return+null;
++++}
}


class+Vertex+{
++++int+value;
++++private+List<Vertex>+adjacentVertices+=+new+ArrayList<Vertex>();

++++public+Vertex(int+v)+{
++++++++this.value+=+v;
++++}

++++public+List<Vertex>+getAdjacentVertices()+{
++++++++return+adjacentVertices;
++++}


++++public+int+getVertexValue()+{
++++++++return+value;
++++}


++++@Override
++++public+boolean+equals(Object+o)+{
++++++++if+(this+==+o)
++++++++++++return+true;
++++++++if+(o+==+null+%7C%7C+getClass()+!=+o.getClass())
++++++++++++return+false;

++++++++Vertex+vertex+=+(Vertex)+o;

++++++++return+value+==+vertex.value;

++++}

++++@Override
++++public+int+hashCode()+{
++++++++return+value;
++++}
}|code-block|syntax|javascript|789370|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|L|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|M|8|@]|9|@]|A|$G|H]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

I came across a similar question where I had to convert one 4 digit prime number 1033 to another 4 digit prime number 3739 in minimum number of steps. I was able to solve the problem, it might not be efficient but here is the working code for the same.

Below code has been written in Java

<pre><code>import java.util.*;

public class PrimeNumberProblem {

 public static void main(String... args) {
 System.out.println("Minimum number of steps required for converting 1033 to 3739 are = "
 + getMinSteps(1033, 3739));
 }

 public static int getMinSteps(int a, int b) {
 if (a == b)
 return 0;

 List&lt;Integer&gt; primes = new ArrayList&lt;&gt;();

 // get all the 4 digit prime numbers
 primes = getPrimeNumbers();

 // consists of graph with vertices as all the prime numbers
 Graph graph = addNumbersToGraph(primes);

 // adding edges to the graph vertices
 Graph finalGraph = addWeightToGraph(graph);

 // min number of steps required
 int result = findShortestRoute(finalGraph.getVertex(a), finalGraph.getVertex(b));

 return result;
 }

 private static int findShortestRoute(Vertex source, Vertex dest) {
 if (source.getVertexValue() == dest.getVertexValue())
 return 0;

 // step 1 Initialize the queue. Also Map to store path
 Queue&lt;Vertex&gt; visitedQueue = new LinkedList&lt;&gt;();
 Map&lt;Vertex, Vertex&gt; currentPrevMap = new HashMap&lt;Vertex, Vertex&gt;();

 // step 2 start from visiting S (starting node), and mark it visited, add to queue
 Map&lt;Integer, Boolean&gt; visited = new HashMap&lt;Integer, Boolean&gt;();
 visited.put(source.getVertexValue(), true);
 visitedQueue.add(source);

 int level = 0;
 // step 3 Repeat until queue is empty
 while (!visitedQueue.isEmpty()) {
 // step 4 remove from queue
 Vertex current = visitedQueue.remove();
 if (current.getVertexValue() == dest.getVertexValue()) {
 printPath(source, dest, currentPrevMap);
 return level;
 } else if (current.getAdjacentVertices().size() &gt; 0) {
 level++;
 }
 // step 5 add each of the unvisited neighbour and mark visited
 for (Vertex adjacentVertex : current.getAdjacentVertices()) {
 Integer value = adjacentVertex.getVertexValue();
 if (value == dest.getVertexValue()) {
 currentPrevMap.put(adjacentVertex, current);
 printPath(source, dest, currentPrevMap);
 return level;
 }
 if (visited.get(value) == null) {
 currentPrevMap.put(adjacentVertex, current);
 // mark visited and enqueue it
 visited.put(value, true);
 visitedQueue.add(adjacentVertex);
 }
 }
 }
 // not found
 System.out.println("Dest vertex not found");
 return -1;
 }

 private static void printPath(Vertex source, Vertex dest, Map&lt;Vertex, Vertex&gt; currentPrevMap) {
 Vertex node = dest;
 System.out.println("Reverse Path from source: " + source.getVertexValue() + " to dest: "
 + dest.getVertexValue());
 while (node != source) {
 System.out.println(node.getVertexValue());
 node = currentPrevMap.get(node);
 }
 System.out.println(source.getVertexValue());
 }

 private static Graph addWeightToGraph(Graph graph) {
 List&lt;Vertex&gt; vertices = graph.getAllVertices();
 for (Vertex i : vertices) {
 for (Vertex j : vertices) {
 if (i.equals(j))
 continue;

 if (distance(i, j) == 1) {
 i.getAdjacentVertices().add(j);
 // i.addEdge(new Edge(i, j, 1));
 }
 }
 }
 return graph;
 }

 private static int distance(Vertex source, Vertex dest) {
 if (source.getVertexValue() == dest.getVertexValue()) {
 return 0;
 }

 char[] numA = extractIntegers(source.getVertexValue());
 char[] numB = extractIntegers(dest.getVertexValue());

 int len1 = numA.length;

 int tracker = 0;

 for (int i = 0; i &lt; len1; i++) {

 if (numA[i] != numB[i]) {
 numA[i] = numB[i];
 tracker++;
 String sA = String.copyValueOf(numA);
 String sB = String.copyValueOf(numB);
 // if we have reached destination
 if (Integer.parseInt(sA) == Integer.parseInt(sB)) {
 return tracker;
 }
 }

 }
 return tracker;
 }

 private static char[] extractIntegers(int i) {
 char[] arr = Integer.toString(i).toCharArray();
 return arr;
 }

 private static Graph addNumbersToGraph(List&lt;Integer&gt; primes) {
 Graph g = new Graph();
 for (Integer prime : primes) {
 g.addVertex(new Vertex(prime));
 }
 return g;
 }

 private static List&lt;Integer&gt; getPrimeNumbers() {
 List&lt;Integer&gt; fourDigitPrimes = new ArrayList&lt;&gt;();
 fourDigitPrimes.add(1033);
 fourDigitPrimes.add(1733);
 fourDigitPrimes.add(3733);
 fourDigitPrimes.add(3739);

 // for (int i = 1000; i &lt; 9999; i++) {
 // if (isPrime(i))
 // fourDigitPrimes.add(i);
 // }

 return fourDigitPrimes;
 }

 private static boolean isPrime(int i) {

 for (int k = 2; k &lt; Math.sqrt(i); k++) {
 if (i % k == 0)
 return false;
 }

 return true;
 }
}


class Graph {
 public List&lt;Vertex&gt; vertexList = new ArrayList&lt;Vertex&gt;();

 public void addVertex(Vertex V) {
 vertexList.add(V);
 }


 public List getAllAdjacentNodes(Vertex V) {
 return V.getAdjacentVertices();
 }

 public List getAllVertices() {
 return vertexList;
 }

 public Vertex getVertex(int val) {
 Iterator&lt;Vertex&gt; keys = vertexList.iterator();
 while (keys.hasNext()) {
 Vertex v = keys.next();
 if (v.getVertexValue() == val)
 return v;
 }
 return null;
 }
}


class Vertex {
 int value;
 private List&lt;Vertex&gt; adjacentVertices = new ArrayList&lt;Vertex&gt;();

 public Vertex(int v) {
 this.value = v;
 }

 public List&lt;Vertex&gt; getAdjacentVertices() {
 return adjacentVertices;
 }


 public int getVertexValue() {
 return value;
 }


 @Override
 public boolean equals(Object o) {
 if (this == o)
 return true;
 if (o == null || getClass() != o.getClass())
 return false;

 Vertex vertex = (Vertex) o;

 return value == vertex.value;

 }

 @Override
 public int hashCode() {
 return value;
 }
}
</code></pre>

blocks|key|2694316|text|这是我使用BFS的解决方案，我已经将所有4位素数保存到一个数组中，因为不需要编写函数来计算质数。我希望它能帮上忙|type|unstyled|depth|inlineStyleRanges|entityRanges|data|2694317|+#include<stdio.h>
+int+hash[10000];
+int+a,b,ans,level,new_num,count;
+int+prime[]+=+{1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,1993,1997,1999,2003,2011,2017,2027,2029,2039,2053,2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,2131,2137,2141,2143,2153,2161,2179,2203,2207,2213,2221,2237,2239,2243,2251,2267,2269,2273,2281,2287,2293,2297,2309,2311,2333,2339,2341,2347,2351,2357,2371,2377,2381,2383,2389,2393,2399,2411,2417,2423,2437,2441,2447,2459,2467,2473,2477,2503,2521,2531,2539,2543,2549,2551,2557,2579,2591,2593,2609,2617,2621,2633,2647,2657,2659,2663,2671,2677,2683,2687,2689,2693,2699,2707,2711,2713,2719,2729,2731,2741,2749,2753,2767,2777,2789,2791,2797,2801,2803,2819,2833,2837,2843,2851,2857,2861,2879,2887,2897,2903,2909,2917,2927,2939,2953,2957,2963,2969,2971,2999,3001,3011,3019,3023,3037,3041,3049,3061,3067,3079,3083,3089,3109,3119,3121,3137,3163,3167,3169,3181,3187,3191,3203,3209,3217,3221,3229,3251,3253,3257,3259,3271,3299,3301,3307,3313,3319,3323,3329,3331,3343,3347,3359,3361,3371,3373,3389,3391,3407,3413,3433,3449,3457,3461,3463,3467,3469,3491,3499,3511,3517,3527,3529,3533,3539,3541,3547,3557,3559,3571,3581,3583,3593,3607,3613,3617,3623,3631,3637,3643,3659,3671,3673,3677,3691,3697,3701,3709,3719,3727,3733,3739,3761,3767,3769,3779,3793,3797,3803,3821,3823,3833,3847,3851,3853,3863,3877,3881,3889,3907,3911,3917,3919,3923,3929,3931,3943,3947,3967,3989,4001,4003,4007,4013,4019,4021,4027,4049,4051,4057,4073,4079,4091,4093,4099,4111,4127,4129,4133,4139,4153,4157,4159,4177,4201,4211,4217,4219,4229,4231,4241,4243,4253,4259,4261,4271,4273,4283,4289,4297,4327,4337,4339,4349,4357,4363,4373,4391,4397,4409,4421,4423,4441,4447,4451,4457,4463,4481,4483,4493,4507,4513,4517,4519,4523,4547,4549,4561,4567,4583,4591,4597,4603,4621,4637,4639,4643,4649,4651,4657,4663,4673,4679,4691,4703,4721,4723,4729,4733,4751,4759,4783,4787,4789,4793,4799,4801,4813,4817,4831,4861,4871,4877,4889,4903,4909,4919,4931,4933,4937,4943,4951,4957,4967,4969,4973,4987,4993,4999,5003,5009,5011,5021,5023,5039,5051,5059,5077,5081,5087,5099,5101,5107,5113,5119,5147,5153,5167,5171,5179,5189,5197,5209,5227,5231,5233,5237,5261,5273,5279,5281,5297,5303,5309,5323,5333,5347,5351,5381,5387,5393,5399,5407,5413,5417,5419,5431,5437,5441,5443,5449,5471,5477,5479,5483,5501,5503,5507,5519,5521,5527,5531,5557,5563,5569,5573,5581,5591,5623,5639,5641,5647,5651,5653,5657,5659,5669,5683,5689,5693,5701,5711,5717,5737,5741,5743,5749,5779,5783,5791,5801,5807,5813,5821,5827,5839,5843,5849,5851,5857,5861,5867,5869,5879,5881,5897,5903,5923,5927,5939,5953,5981,5987,6007,6011,6029,6037,6043,6047,6053,6067,6073,6079,6089,6091,6101,6113,6121,6131,6133,6143,6151,6163,6173,6197,6199,6203,6211,6217,6221,6229,6247,6257,6263,6269,6271,6277,6287,6299,6301,6311,6317,6323,6329,6337,6343,6353,6359,6361,6367,6373,6379,6389,6397,6421,6427,6449,6451,6469,6473,6481,6491,6521,6529,6547,6551,6553,6563,6569,6571,6577,6581,6599,6607,6619,6637,6653,6659,6661,6673,6679,6689,6691,6701,6703,6709,6719,6733,6737,6761,6763,6779,6781,6791,6793,6803,6823,6827,6829,6833,6841,6857,6863,6869,6871,6883,6899,6907,6911,6917,6947,6949,6959,6961,6967,6971,6977,6983,6991,6997,7001,7013,7019,7027,7039,7043,7057,7069,7079,7103,7109,7121,7127,7129,7151,7159,7177,7187,7193,7207,7211,7213,7219,7229,7237,7243,7247,7253,7283,7297,7307,7309,7321,7331,7333,7349,7351,7369,7393,7411,7417,7433,7451,7457,7459,7477,7481,7487,7489,7499,7507,7517,7523,7529,7537,7541,7547,7549,7559,7561,7573,7577,7583,7589,7591,7603,7607,7621,7639,7643,7649,7669,7673,7681,7687,7691,7699,7703,7717,7723,7727,7741,7753,7757,7759,7789,7793,7817,7823,7829,7841,7853,7867,7873,7877,7879,7883,7901,7907,7919,7927,7933,7937,7949,7951,7963,7993,8009,8011,8017,8039,8053,8059,8069,8081,8087,8089,8093,8101,8111,8117,8123,8147,8161,8167,8171,8179,8191,8209,8219,8221,8231,8233,8237,8243,8263,8269,8273,8287,8291,8293,8297,8311,8317,8329,8353,8363,8369,8377,8387,8389,8419,8423,8429,8431,8443,8447,8461,8467,8501,8513,8521,8527,8537,8539,8543,8563,8573,8581,8597,8599,8609,8623,8627,8629,8641,8647,8663,8669,8677,8681,8689,8693,8699,8707,8713,8719,8731,8737,8741,8747,8753,8761,8779,8783,8803,8807,8819,8821,8831,8837,8839,8849,8861,8863,8867,8887,8893,8923,8929,8933,8941,8951,8963,8969,8971,8999,9001,9007,9011,9013,9029,9041,9043,9049,9059,9067,9091,9103,9109,9127,9133,9137,9151,9157,9161,9173,9181,9187,9199,9203,9209,9221,9227,9239,9241,9257,9277,9281,9283,9293,9311,9319,9323,9337,9341,9343,9349,9371,9377,9391,9397,9403,9413,9419,9421,9431,9433,9437,9439,9461,9463,9467,9473,9479,9491,9497,9511,9521,9533,9539,9547,9551,9587,9601,9613,9619,9623,9629,9631,9643,9649,9661,9677,9679,9689,9697,9719,9721,9733,9739,9743,9749,9767,9769,9781,9787,9791,9803,9811,9817,9829,9833,9839,9851,9857,9859,9871,9883,9887,9901,9907,9923,9929,9931,9941,9949,9967,9973};
int+size+=+sizeof(prime)/sizeof(prime[0]);
int+bfs(int,int);
typedef+struct+q{
int+x,+c;
+}+queue;
queue+qq[10000];

int+isprime(int+x)
{

+++int+l,r,m;
+l=m=0;+r=size-1;
+while+(l+<=+r)
{
+int+m+=+l+%2B+(r-l)/2;
+if+(prime[m]+==+x)
++++return+1;
+if+(prime[m]+<+x)
++++l+=+m+%2B+1;
else
+++++r+=+m+-+1;
+}
++return+0;
+}

+int+bfs(int+num1,int+num2)
+{
+int+i,j,k,p,q,n;
++new_num=p=q=0;
++i=0;
++j=1;
++qq[i].x+=+num1;
++qq[i].c+=+0;
++hash[num1]+=+1;
++while(i!=j)
++{+++n+=+qq[i].x;
++++level+=+qq[i].c;
++++if(n==num2)
++++{
++++++++count+=+level;
++++++++++return+count;
++++}
++++level%2B%2B;
++++p+=+n%251000;
++++++++for(k=1;k<10;k%2B%2B)
++++++++{++new_num+=+(k*1000)%2B+p;
++++++++++++if(isprime(new_num)&&(new_num!=n)&&(!hash[new_num]))
++++++++++++{
++++++++++++++++hash[new_num]+=+1;
+++++++++++++++++qq[j].x+=+new_num;
+++++++++++++++++qq[j].c+=+level;
++++++++++++++++++j%2B%2B;


++++++++++++}}
++++++++p=q=new_num=0;

+++++p+=+n/1000;
++++++++q+=+n%25100;
++++++for(k=0;k<10;k%2B%2B)
++++++++{++new_num+=+(p*1000)%2Bk*100%2Bq;
++++++++++++if(isprime(new_num)&&(new_num!=n)&&(!hash[new_num]))
++++++++++++{
+++++++++++++++hash[new_num]+=+1;
+++++++++++++++++qq[j].x+=+new_num;
+++++++++++++++++qq[j].c+=+level;
+++++++++++++++++j%2B%2B;
+++++++++++++++++}}
++p=q=new_num=0;

+++p+=+n/100;
+++q+=+n%2510;
+++for(k=0;k<10;k%2B%2B)
++++++++{++new_num+=+(p*100)%2Bk*10%2Bq;
++++++++++++if(isprime(new_num)&&(new_num!=n)&&(!hash[new_num]))
++++++++++++{
++++++++++++++++hash[new_num]+=+1;
+++++++++++++++++qq[j].x+=+new_num;
+++++++++++++++++qq[j].c+=+level;
+++++++++++++++++j%2B%2B;
++++++++++++++++}}
+++p=q=new_num=0;
+++p+++=+n/10;
+++for(k=0;k<10;k%2B%2B)
++++++++{++new_num+=+(p*10)%2Bk;
++++++++++++if(isprime(new_num)&&(new_num!=n)&&(!hash[new_num]))
++++++++++++{
++++++++++++++++hash[new_num]+=+1;
+++++++++++++++++qq[j].x+=+new_num;
+++++++++++++++++qq[j].c+=+level;
+++++++++++++++++j%2B%2B;
++++++++++++++++}}
+++++p=q=new_num=0;
++++i%2B%2B;

+++++}
+++++return+-1;}


++int+main()
+++{
++++int+v,tc;
++++setbuf(stdout,NULL);
++++scanf("%25d",&tc);
++++for(v=1;v<=tc;v%2B%2B)
++++{++int+i,j;
++++a=b=ans=level=new_num=count=0;
++++for(i=0;i<10000;i%2B%2B)
++++{qq[i].x=0;
++++++qq[i].c=0;
++++++hash[i]=0;}

++++scanf("%25d%25d",&a,&b);

++++if(a==b)
++++{+ans+=+0;}
++++else
++++{+ans+=+bfs(a,b);}
++++printf("Case+#%25d\n",+v);
++++if(ans==-1)
+++{
++++printf("Impossible\n");

++++}
++++else
+++{printf("%25d\n",ans);}

++++}
++++return+0;
++++}|code-block|syntax|javascript|2694318|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Here is my solution using BFS and I have already saved all 4 digit prime numbers into an array as there is no need to write a function to calculate the prime numbers. I hope it helps

<pre><code> #include&lt;stdio.h&gt;
 int hash[10000];
 int a,b,ans,level,new_num,count;
 int prime[] = {1009,1013,1019,1021,1031,1033,1039,1049,1051,1061,1063,1069,1087,1091,1093,1097,1103,1109,1117,1123,1129,1151,1153,1163,1171,1181,1187,1193,1201,1213,1217,1223,1229,1231,1237,1249,1259,1277,1279,1283,1289,1291,1297,1301,1303,1307,1319,1321,1327,1361,1367,1373,1381,1399,1409,1423,1427,1429,1433,1439,1447,1451,1453,1459,1471,1481,1483,1487,1489,1493,1499,1511,1523,1531,1543,1549,1553,1559,1567,1571,1579,1583,1597,1601,1607,1609,1613,1619,1621,1627,1637,1657,1663,1667,1669,1693,1697,1699,1709,1721,1723,1733,1741,1747,1753,1759,1777,1783,1787,1789,1801,1811,1823,1831,1847,1861,1867,1871,1873,1877,1879,1889,1901,1907,1913,1931,1933,1949,1951,1973,1979,1987,1993,1997,1999,2003,2011,2017,2027,2029,2039,2053,2063,2069,2081,2083,2087,2089,2099,2111,2113,2129,2131,2137,2141,2143,2153,2161,2179,2203,2207,2213,2221,2237,2239,2243,2251,2267,2269,2273,2281,2287,2293,2297,2309,2311,2333,2339,2341,2347,2351,2357,2371,2377,2381,2383,2389,2393,2399,2411,2417,2423,2437,2441,2447,2459,2467,2473,2477,2503,2521,2531,2539,2543,2549,2551,2557,2579,2591,2593,2609,2617,2621,2633,2647,2657,2659,2663,2671,2677,2683,2687,2689,2693,2699,2707,2711,2713,2719,2729,2731,2741,2749,2753,2767,2777,2789,2791,2797,2801,2803,2819,2833,2837,2843,2851,2857,2861,2879,2887,2897,2903,2909,2917,2927,2939,2953,2957,2963,2969,2971,2999,3001,3011,3019,3023,3037,3041,3049,3061,3067,3079,3083,3089,3109,3119,3121,3137,3163,3167,3169,3181,3187,3191,3203,3209,3217,3221,3229,3251,3253,3257,3259,3271,3299,3301,3307,3313,3319,3323,3329,3331,3343,3347,3359,3361,3371,3373,3389,3391,3407,3413,3433,3449,3457,3461,3463,3467,3469,3491,3499,3511,3517,3527,3529,3533,3539,3541,3547,3557,3559,3571,3581,3583,3593,3607,3613,3617,3623,3631,3637,3643,3659,3671,3673,3677,3691,3697,3701,3709,3719,3727,3733,3739,3761,3767,3769,3779,3793,3797,3803,3821,3823,3833,3847,3851,3853,3863,3877,3881,3889,3907,3911,3917,3919,3923,3929,3931,3943,3947,3967,3989,4001,4003,4007,4013,4019,4021,4027,4049,4051,4057,4073,4079,4091,4093,4099,4111,4127,4129,4133,4139,4153,4157,4159,4177,4201,4211,4217,4219,4229,4231,4241,4243,4253,4259,4261,4271,4273,4283,4289,4297,4327,4337,4339,4349,4357,4363,4373,4391,4397,4409,4421,4423,4441,4447,4451,4457,4463,4481,4483,4493,4507,4513,4517,4519,4523,4547,4549,4561,4567,4583,4591,4597,4603,4621,4637,4639,4643,4649,4651,4657,4663,4673,4679,4691,4703,4721,4723,4729,4733,4751,4759,4783,4787,4789,4793,4799,4801,4813,4817,4831,4861,4871,4877,4889,4903,4909,4919,4931,4933,4937,4943,4951,4957,4967,4969,4973,4987,4993,4999,5003,5009,5011,5021,5023,5039,5051,5059,5077,5081,5087,5099,5101,5107,5113,5119,5147,5153,5167,5171,5179,5189,5197,5209,5227,5231,5233,5237,5261,5273,5279,5281,5297,5303,5309,5323,5333,5347,5351,5381,5387,5393,5399,5407,5413,5417,5419,5431,5437,5441,5443,5449,5471,5477,5479,5483,5501,5503,5507,5519,5521,5527,5531,5557,5563,5569,5573,5581,5591,5623,5639,5641,5647,5651,5653,5657,5659,5669,5683,5689,5693,5701,5711,5717,5737,5741,5743,5749,5779,5783,5791,5801,5807,5813,5821,5827,5839,5843,5849,5851,5857,5861,5867,5869,5879,5881,5897,5903,5923,5927,5939,5953,5981,5987,6007,6011,6029,6037,6043,6047,6053,6067,6073,6079,6089,6091,6101,6113,6121,6131,6133,6143,6151,6163,6173,6197,6199,6203,6211,6217,6221,6229,6247,6257,6263,6269,6271,6277,6287,6299,6301,6311,6317,6323,6329,6337,6343,6353,6359,6361,6367,6373,6379,6389,6397,6421,6427,6449,6451,6469,6473,6481,6491,6521,6529,6547,6551,6553,6563,6569,6571,6577,6581,6599,6607,6619,6637,6653,6659,6661,6673,6679,6689,6691,6701,6703,6709,6719,6733,6737,6761,6763,6779,6781,6791,6793,6803,6823,6827,6829,6833,6841,6857,6863,6869,6871,6883,6899,6907,6911,6917,6947,6949,6959,6961,6967,6971,6977,6983,6991,6997,7001,7013,7019,7027,7039,7043,7057,7069,7079,7103,7109,7121,7127,7129,7151,7159,7177,7187,7193,7207,7211,7213,7219,7229,7237,7243,7247,7253,7283,7297,7307,7309,7321,7331,7333,7349,7351,7369,7393,7411,7417,7433,7451,7457,7459,7477,7481,7487,7489,7499,7507,7517,7523,7529,7537,7541,7547,7549,7559,7561,7573,7577,7583,7589,7591,7603,7607,7621,7639,7643,7649,7669,7673,7681,7687,7691,7699,7703,7717,7723,7727,7741,7753,7757,7759,7789,7793,7817,7823,7829,7841,7853,7867,7873,7877,7879,7883,7901,7907,7919,7927,7933,7937,7949,7951,7963,7993,8009,8011,8017,8039,8053,8059,8069,8081,8087,8089,8093,8101,8111,8117,8123,8147,8161,8167,8171,8179,8191,8209,8219,8221,8231,8233,8237,8243,8263,8269,8273,8287,8291,8293,8297,8311,8317,8329,8353,8363,8369,8377,8387,8389,8419,8423,8429,8431,8443,8447,8461,8467,8501,8513,8521,8527,8537,8539,8543,8563,8573,8581,8597,8599,8609,8623,8627,8629,8641,8647,8663,8669,8677,8681,8689,8693,8699,8707,8713,8719,8731,8737,8741,8747,8753,8761,8779,8783,8803,8807,8819,8821,8831,8837,8839,8849,8861,8863,8867,8887,8893,8923,8929,8933,8941,8951,8963,8969,8971,8999,9001,9007,9011,9013,9029,9041,9043,9049,9059,9067,9091,9103,9109,9127,9133,9137,9151,9157,9161,9173,9181,9187,9199,9203,9209,9221,9227,9239,9241,9257,9277,9281,9283,9293,9311,9319,9323,9337,9341,9343,9349,9371,9377,9391,9397,9403,9413,9419,9421,9431,9433,9437,9439,9461,9463,9467,9473,9479,9491,9497,9511,9521,9533,9539,9547,9551,9587,9601,9613,9619,9623,9629,9631,9643,9649,9661,9677,9679,9689,9697,9719,9721,9733,9739,9743,9749,9767,9769,9781,9787,9791,9803,9811,9817,9829,9833,9839,9851,9857,9859,9871,9883,9887,9901,9907,9923,9929,9931,9941,9949,9967,9973};
int size = sizeof(prime)/sizeof(prime[0]);
int bfs(int,int);
typedef struct q{
int x, c;
 } queue;
queue qq[10000];

int isprime(int x)
{

 int l,r,m;
 l=m=0; r=size-1;
 while (l &lt;= r)
{
 int m = l + (r-l)/2;
 if (prime[m] == x)
 return 1;
 if (prime[m] &lt; x)
 l = m + 1;
else
 r = m - 1;
 }
 return 0;
 }

 int bfs(int num1,int num2)
 {
 int i,j,k,p,q,n;
 new_num=p=q=0;
 i=0;
 j=1;
 qq[i].x = num1;
 qq[i].c = 0;
 hash[num1] = 1;
 while(i!=j)
 { n = qq[i].x;
 level = qq[i].c;
 if(n==num2)
 {
 count = level;
 return count;
 }
 level++;
 p = n%1000;
 for(k=1;k&lt;10;k++)
 { new_num = (k*1000)+ p;
 if(isprime(new_num)&amp;&amp;(new_num!=n)&amp;&amp;(!hash[new_num]))
 {
 hash[new_num] = 1;
 qq[j].x = new_num;
 qq[j].c = level;
 j++;


 }}
 p=q=new_num=0;

 p = n/1000;
 q = n%100;
 for(k=0;k&lt;10;k++)
 { new_num = (p*1000)+k*100+q;
 if(isprime(new_num)&amp;&amp;(new_num!=n)&amp;&amp;(!hash[new_num]))
 {
 hash[new_num] = 1;
 qq[j].x = new_num;
 qq[j].c = level;
 j++;
 }}
 p=q=new_num=0;

 p = n/100;
 q = n%10;
 for(k=0;k&lt;10;k++)
 { new_num = (p*100)+k*10+q;
 if(isprime(new_num)&amp;&amp;(new_num!=n)&amp;&amp;(!hash[new_num]))
 {
 hash[new_num] = 1;
 qq[j].x = new_num;
 qq[j].c = level;
 j++;
 }}
 p=q=new_num=0;
 p = n/10;
 for(k=0;k&lt;10;k++)
 { new_num = (p*10)+k;
 if(isprime(new_num)&amp;&amp;(new_num!=n)&amp;&amp;(!hash[new_num]))
 {
 hash[new_num] = 1;
 qq[j].x = new_num;
 qq[j].c = level;
 j++;
 }}
 p=q=new_num=0;
 i++;

 }
 return -1;}


 int main()
 {
 int v,tc;
 setbuf(stdout,NULL);
 scanf("%d",&amp;tc);
 for(v=1;v&lt;=tc;v++)
 { int i,j;
 a=b=ans=level=new_num=count=0;
 for(i=0;i&lt;10000;i++)
 {qq[i].x=0;
 qq[i].c=0;
 hash[i]=0;}

 scanf("%d%d",&amp;a,&amp;b);

 if(a==b)
 { ans = 0;}
 else
 { ans = bfs(a,b);}
 printf("Case #%d\n", v);
 if(ans==-1)
 {
 printf("Impossible\n");

 }
 else
 {printf("%d\n",ans);}

 }
 return 0;
 }
</code></pre>

blocks|key|4158259|text|我的使用BFS的Python解决方案：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4158260|++++import+queue
++++#+Class+to+represent+a+graph
++++class+Graph:
++++++++def+__init__(self,+V):
++++++++++++self.V+=+V++#+No.+of+vertices
++++++++++++self.prime_list+=+[[]+for+i+in+range(V)]
++++#+function+to+add+an+edge+to+graph
++++def+addedge(self,+V1,+V2):
++++++++self.prime_list[V1].append(V2)
++++++++self.prime_list[V2].append(V1)

++++def+bfs(self,+in1,+in2):
++++++++visited+=+[0]+*+self.V
++++++++que+=+queue.Queue()
++++++++visited[in1]+=+1
++++++++que.put(in1)
++++++++while+not+que.empty():
++++++++++++prime_index+=+que.get()
++++++++++++i+=+0
++++++++++++while+i+<+len(self.prime_list[prime_index]):
++++++++++++++++if+not+visited[self.prime_list[prime_index][i]]:
++++++++++++++++++++visited[self.prime_list[prime_index][i]]+=+visited[prime_index]+%2B+1
++++++++++++++++++++que.put(self.prime_list[prime_index][i])
++++++++++++++++if+self.prime_list[prime_index][i]+==+in2:
++++++++++++++++++++return+visited[self.prime_list[prime_index][i]]+-+1
++++++++++++++++i+%2B=+1


#+//+Finding+all+4+digit+prime+numbers
def+SieveOfEratosthenes(v):
++++#+Create+a+boolean+array+"prime[0..n]"+and+initialize+all+entries+it+as+true.+A+value+in+prime[i]+will+be
++++#+finally+be+false+if+i+is+Not+a+prime,+else+true.
++++n+=+9999
++++prime+=+[True]+*+(n+%2B+1)
++++p+=+2
++++while+p+*+p+<=+9999:
++++++++if+prime[p]:
++++++++++++i+=+p+*+p
++++++++++++while+i+<=+9999:
++++++++++++++++prime[i]+=+False
++++++++++++++++i+=+i+%2B+p
++++++++p+=+p+%2B+1
++++#+v+=+[]
++++for+i+in+range(1000,+n+%2B+1):
++++++++if+prime[i]:
++++++++++++v.append(i)
++++return+v


def+compare(a,+b):
++++diff+=+0
++++while+a:
++++++++if+a+%25+10+!=+b+%25+10:
++++++++++++diff+%2B=+1
++++++++a+//=+10
++++++++b+//=+10
++++#+If+the+numbers+differ+only+by+a+single+#+digit+return+true+else+false
++++if+diff+>+1:
++++++++return+False
++++return+True


def+shortestPath(num1,+num2):
++++#+Generate+all+4+digit
++++pset+=+[]
++++SieveOfEratosthenes(pset)
++++#+Create+a+graph+where+node+numbers+#+are+indexes+in+pset[]+and+there+is
++++#+an+edge+between+two+nodes+only+if+#+they+differ+by+single+digit.
++++g+=+Graph(len(pset))
++++for+i+in+range(len(pset)):
++++++++for+j+in+range(i+%2B+1,+len(pset)):
++++++++++++if+compare(pset[i],+pset[j]):
++++++++++++++++g.addedge(i,+j)
++++#+Since+graph+nodes+represent+indexes+#+of+numbers+in+pset[],+we+find+indexes+of+num1+and+num2.
++++in1,+in2+=+None,+None
++++for+j+in+range(len(pset)):
++++++++if+pset[j]+==+num1:
++++++++++++in1+=+j
++++for+j+in+range(len(pset)):
++++++++if+pset[j]+==+num2:
++++++++++++in2+=+j
++++return+g.bfs(in1,+in2)


#+Driver+code
if+__name__+==+'__main__':
++++num1+=+1033
++++num2+=+8179
++++print(shortestPath(num1,+num2))|code-block|syntax|javascript|4158261|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

My Python solution using BFS:

<pre><code> import queue
 # Class to represent a graph
 class Graph:
 def __init__(self, V):
 self.V = V # No. of vertices
 self.prime_list = [[] for i in range(V)]
 # function to add an edge to graph
 def addedge(self, V1, V2):
 self.prime_list[V1].append(V2)
 self.prime_list[V2].append(V1)

 def bfs(self, in1, in2):
 visited = [0] * self.V
 que = queue.Queue()
 visited[in1] = 1
 que.put(in1)
 while not que.empty():
 prime_index = que.get()
 i = 0
 while i &lt; len(self.prime_list[prime_index]):
 if not visited[self.prime_list[prime_index][i]]:
 visited[self.prime_list[prime_index][i]] = visited[prime_index] + 1
 que.put(self.prime_list[prime_index][i])
 if self.prime_list[prime_index][i] == in2:
 return visited[self.prime_list[prime_index][i]] - 1
 i += 1


# // Finding all 4 digit prime numbers
def SieveOfEratosthenes(v):
 # Create a boolean array "prime[0..n]" and initialize all entries it as true. A value in prime[i] will be
 # finally be false if i is Not a prime, else true.
 n = 9999
 prime = [True] * (n + 1)
 p = 2
 while p * p &lt;= 9999:
 if prime[p]:
 i = p * p
 while i &lt;= 9999:
 prime[i] = False
 i = i + p
 p = p + 1
 # v = []
 for i in range(1000, n + 1):
 if prime[i]:
 v.append(i)
 return v


def compare(a, b):
 diff = 0
 while a:
 if a % 10 != b % 10:
 diff += 1
 a //= 10
 b //= 10
 # If the numbers differ only by a single # digit return true else false
 if diff &gt; 1:
 return False
 return True


def shortestPath(num1, num2):
 # Generate all 4 digit
 pset = []
 SieveOfEratosthenes(pset)
 # Create a graph where node numbers # are indexes in pset[] and there is
 # an edge between two nodes only if # they differ by single digit.
 g = Graph(len(pset))
 for i in range(len(pset)):
 for j in range(i + 1, len(pset)):
 if compare(pset[i], pset[j]):
 g.addedge(i, j)
 # Since graph nodes represent indexes # of numbers in pset[], we find indexes of num1 and num2.
 in1, in2 = None, None
 for j in range(len(pset)):
 if pset[j] == num1:
 in1 = j
 for j in range(len(pset)):
 if pset[j] == num2:
 in2 = j
 return g.bfs(in1, in2)


# Driver code
if __name__ == '__main__':
 num1 = 1033
 num2 = 8179
 print(shortestPath(num1, num2))
</code></pre>

I thought it would be a fun problem: <a href="https://www.spoj.pl/problems/PPATH/" rel="nofollow noreferrer">Prime Path</a>

But...It is hard for me.
My only idea is "To do something with knapsack problem".. and no other ideas.
Could You track me for good way?
It's not for any challenge or University homework. I just want to learn something.

_

Ok, but firstly, how to find this prime numbers? Do i need to find all 4digit prime numbers, add it to graph?

For now i have generating all prime numbers.

<a href="http://pastebin.com/wbhRNRHQ" rel="nofollow noreferrer">http://pastebin.com/wbhRNRHQ</a>

Could You give me sample code to declare graph build on neighbour list?

Help with algorithm problem from SPOJ

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

我认为这将是一个有趣的问题：But...It对我来说很难。我唯一的想法是“解决背包问题”..没有其他的想法。你能以好的方式跟踪我吗？这不是为了任何挑战或大学家庭作业。我只是想学点东西。_好的，但是首先，如何找到这个质数？我是否需要找到所有4位素数，并将其添加到图中？现在，我已经生成了所有的质数。你能给我在邻居列表上声明...

问帮助解决来自SPOJ的算法问题
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问帮助解决来自SPOJ的算法问题EN