http://www.spoj.com/problems/PPATH/
We will solve this with BFS( if you need some more info about BFS go here). First of all we need to find all the prime numbers up to 10000 we can do this easily with the sieve of Eratostenes( for more info about the sieve of Eratostenes go here). We will keep a queue where we will add the number which we have already created , the numbers are always 4 digit which makes our job easier. Now we need to replace all the digits with a different digit from 0 to 9 (be careful while replacing the first digit you might end up replacing the first digit with 0 :) ). Every time when we take out the current number from our queue we need to separate his 4 digits and then keep replacing and combing the digits back to form other numbers, then with the help of the found prime numbers we can check if the number is prime or not, and also don't forget to mark every number you get so that your program won't process the same numbers all over again. Also check the source code for a better understanding.
We will solve this with BFS( if you need some more info about BFS go here). First of all we need to find all the prime numbers up to 10000 we can do this easily with the sieve of Eratostenes( for more info about the sieve of Eratostenes go here). We will keep a queue where we will add the number which we have already created , the numbers are always 4 digit which makes our job easier. Now we need to replace all the digits with a different digit from 0 to 9 (be careful while replacing the first digit you might end up replacing the first digit with 0 :) ). Every time when we take out the current number from our queue we need to separate his 4 digits and then keep replacing and combing the digits back to form other numbers, then with the help of the found prime numbers we can check if the number is prime or not, and also don't forget to mark every number you get so that your program won't process the same numbers all over again. Also check the source code for a better understanding.
Link is not working bro
ReplyDeleteHI
DeleteThe links works perfectly. When you open it a little ad page pops up which takes only 5 seconds to go, after those 5 second you need to click "skip this ad" and you will be on the code page.
Link doesn't work..Shows blocked by govt...
ReplyDelete