+ 10

[ASSIGNMENT] Cyclic Prime Numbers

Prime Number is considered to be a Cyclic Prime Number if all other numbers obtained by cyclic permutation of its digits are also Primes. For example: 197 -> 971 -> 719 P.S. Let's consider single digit Primes also as Cyclic Primes. TASK 1: Check if given number N is a Cyclic Prime Numbers. Input: 31 Output: True TASK 2: For given values A and B print all Cyclic Prime Numbers grouped by related numbers those all cyclic permutations are in a range from A to B. Input: 100 999 Output: ...find it... :-)

26th Apr 2018, 3:13 AM
Nevfy
36 Answers
+ 9
One week past from the assignment publication, so I as usual conclude it with a list of accepted solutions: TASK 1 AND TASK 2: @LukArToDo (range 1-10^5, ML) [kt] : https://code.sololearn.com/cLMmn14j1KrF/?ref=app @Russ (range 1-3*10^5, ML) [Python, beauty output] : https://code.sololearn.com/ccwFC6eIbczq/?ref=app @Nevfy (range 1-10^6, ML) [Python, beauty output] : https://code.sololearn.com/c822zCD51vLJ/?ref=app @~ swim ~ (range 1-4*10^6, TL) [C++] : https://code.sololearn.com/cUqJ9nZhMwMR/?ref=app TASK 1: @VcC [Python, oneliner] : https://code.sololearn.com/c6F730oI34kl/?ref=app TASK 2: @Zoetic Zeel (range 1-10^4, ML) [Python, oneliner] : https://code.sololearn.com/cSfTa5tkDTa3/?ref=app P.S. Ranges are given only to demonstrate the productivity of used algorithms, however you can not really relay on these values while comparing solutions written on different programming languages. Thanks everyone who participated! All codes are very well made and demonstrate different approaches to perform this challenge.
2nd May 2018, 2:20 AM
Nevfy
24th Aug 2018, 8:19 PM
Sumit Programmer😎😎
Sumit Programmer😎😎 - avatar
+ 15
https://code.sololearn.com/cLMmn14j1KrF/?ref=app
28th Apr 2018, 7:45 AM
LukArToDo
LukArToDo - avatar
+ 14
Nevfy Thank you 😊 Your comments are always helpful 😉
28th Apr 2018, 10:12 PM
LukArToDo
LukArToDo - avatar
+ 5
Here is one liner..😀😉 //updated https://code.sololearn.com/cSfTa5tkDTa3/?ref=app
26th Apr 2018, 6:13 AM
Zoetic_Zeel
Zoetic_Zeel - avatar
26th Apr 2018, 5:33 PM
Russ
Russ - avatar
+ 5
@Zoetic Zeel Finally you have done it for the Task 2! And it is an oneliner, amazing! However its complexity is so huge that it even can't find Cyclic Primes with just 4 digits, but that's quite common drawback of using oneliners. Congratulations anyway! The scope of solutions for the assignment wouldn't be full is no one proposed an one line solution. :-)
28th Apr 2018, 12:29 AM
Nevfy
+ 4
@~ swim ~ My congratulations! You are the first one, who fully solved the challenge! It passed successfully through all my tests and I didn't find any weak places in the code. If anyone find some bugs in it - let us know, so we will ask Swim to correct them ;-) P.S. About number 2. Yes, sometimes it happens. I saw that you had this check in Prime check function, but in a wrong place. You firstly kicked out all even numbers returning False and only then checked if the number is equal 2 to return True. :-)
27th Apr 2018, 2:21 PM
Nevfy
+ 4
@Russ Yes, I confirm that now your code is correct and you successfully solved this challenge. My congratulations!
28th Apr 2018, 12:11 AM
Nevfy
+ 4
@LukArToDo Very well done! It seems that you took into account all my previous comments and produced successful code from the first try! Congratulations!
28th Apr 2018, 9:58 PM
Nevfy
+ 4
Almost one week past from the assignment publication and it seems that everyone who wanted to participate have already done it. Here is my own solution for this challenge: https://code.sololearn.com/c822zCD51vLJ/?ref=app One interesting thing that I wanted from you to find (and some of you successfully did it) that Cyclic Prime number can consist only from 1, 3, 7 and 9 digits (unless 2 and 5 which are single digit Cyclic Primes). This fact allows speed up solutions for both tasks. For the TASK 1 it check if the number is Prime and if so consequently check each of its cyclic permutations as well. The worst complexity is about O(sqrt(N)*log10(N)). It also uses filtering techniques that I described above to speed up the solution. For TASK 2 it generates list of Primes in given range, then filter it checking digits of Prime numbers to be only 1, 3, 7 and 9, and then for each number it searches if all of its cyclic permutations are in the same list (if so it removes values from the list that speed up also a search for further numbers). It is hard to estimate a complexity of this method, but I believe that it works quicker than one by one check for all numbers in a given range. And one more benefit from such solution is that numbers are really grouped and can be printed out together!
1st May 2018, 12:56 AM
Nevfy
+ 3
@VcC Very good! However, you missed one point, which makes Task 2 more difficult than you expected. By the way, I formulated it like that especially to avoid simple realizations based on the results from Task 1 like you did. The thing is that for the range 200 1000 you should not print 991, because not ALL of its cyclic permutations are in range from 200 to 1000. You see? :-)
26th Apr 2018, 2:11 PM
Nevfy
+ 3
@Russ That's very close to full solution for the challenge! I like an idea to use a sieve for the Task 2 (however, it is to much for Task 1 due to big complexity, you can thing about easier approach, but you can also keep it like you have). I use it in my solution as well. Especially I like that you understood that if number contains some specific digits you can quickly say that it is not Cyclic Prime. That approach speeds up a lot and I also use if in my solution. However, it seems to me, that you can gain more from that fact for the code for the Task 1... Moreover, due to your realization of cycleNums() function, your code crashes for the input "107" and using this filter you can avoid this situation (otherwise you should rewrite your cycleNums() function). Good luck with corrections!
26th Apr 2018, 7:23 PM
Nevfy
+ 3
@~ swim ~ Yes, @VcC gave you a correct answer (thanks by the way). Your code seems to be almost correct. Your Prime check (and further Cyclic Prime check) returns False for 2. That's right that you can increase performance of your code avoiding multiple checks. Right now solving Task 2 you do a check that all numbers from sequence 197 -> 971 -> 719 are Primes and then you repeat it for twice more while checking 719 and 971. Your Prime check is O(sqrt(N)) - time consuming operation. You correctly mentioned in your code that memoization can help. If you find one number to be a Cyclic Prime you can add all its cyclic permutations (which are higher than this number) to a special list and then on every iteration check if your new number to check is already in this list (if so you quickly return True and remove this number from a list to reduce its length). I believe it will work quicker.
27th Apr 2018, 12:53 AM
Nevfy
+ 3
@~ swim ~ The trick is that it works not only for ending digit but for all digit! "Prime Number is considered to be a Cyclic Prime Number if all other numbers obtained by cyclic permutation of its digits are also Primes." It means that if number has, for example, digit '5' somewhere for one of its cyclic permutations it will be the ending digit, so the number will not be Prime, so the initial number is not Cyclic Prime. You see the trick? :-) I can quickly say that number "567766543334566333321" is not Cyclic Prime just because it has digit '2' in it, so I don't need even start to check whenever this randomly typed number is Prime or not.
1st May 2018, 1:56 AM
Nevfy
+ 1
@Zoetic Zeel Thanks for participation! That's a good start, but for a moment this is wrong. Due to the fact that you check all permutations but not only ciclic permutations your code doesn't find the Cyclic Prime Number 197 (and related to it), which I gave in challenge description as an example.
26th Apr 2018, 1:58 PM
Nevfy
+ 1
@Zoetic Zeel It is much better, however it is still not correct. See the comment I gave to first version of VcC's code above. The thing is that for the range 200 1000 you should not print 991, because not ALL of its cyclic permutations are in range from 200 to 1000!
26th Apr 2018, 6:13 PM
Nevfy
+ 1
@VcC It is going right way! For a moment, there are several bugs: Task 1. Function returns 1 to be a Cyclic Prime, however it is not. Task 2. A. Try range [12 733]. It makes appear both bugs that you have. From lower boundary it still returns 11, however it is now out of the range. From higher boundary it doesn't return 733 itself in the list, however all its permutations are presented. B. For the range [200 900] number 311 is still in the output (it should not be there).
26th Apr 2018, 6:50 PM
Nevfy
+ 1
not included
26th Apr 2018, 9:00 PM
VcC
VcC - avatar