Problem 37 - Truncatable Primes
Today I'm gonna try and solve another challenge from Project Euler - site with various programming tasks heavily connected with mathematics. If you're learning any new programming language and don't have any ideas for new programs - just head over to this site, complete as many challenges as you can and you'll definitely improve your skills. Just take a look at this task:
How to start?
Best way to solve any problem is to divide it into many smaller ones - that way you will have to 'glue' these parts together into one and you'll hopefully have fully functioning solution. In this problem I want to firstly complete this smaller problems:
- Check if a number is prime
- Truncate the number from left and from right
- Check if every result from truncating is also a prime
As I'm currently learning C++ this solution will be written in this language, but you can easily convert it to the Python version after understanding the concept. Completing these 3 problems will let us complete this challenge so without wasting time let's move to the first one.
How to check if a number is a prime? Consider this example:
We've got some number x that we want to check. Now if we run a loop from 1 to the x, then on every iteration perform operation x modulo i. If the result is different than 0 for every number, then it's a prime, if not then it's not.
But as you may think, it will be really slow for bigger numbers, so we will have to speed up this algorithm. Firstly check if the number is smaller or equall to one, if so this number cannot be prime (remember that 1 is not a prime). Then assure that 2 and 3 are prime numbers. Also if you take a look at group of prime numbers, none of them are divisable by 2 so quickly checking it in a first place will make it run a little bit faster. Lastly run the checking loop.
Quick note from the future!
This version of algorithm took a few minuts to finish, but without any ideas how to make it faster, I looked at some other algorithms. That's the improved version of the checking loop:
Runs in around second ;)
Now we have to check, if after removing every digit from left, or right, it will still be a prime. If that was Python I would write this function in a few lines but not today, not that easy ;)
After tinkering with it for a little bit I came up with this idea. If you have integer ex 152 and divide it by 10 then the result will be 15. Same as removing the last number, right? Remember that you have to do this on integers as if it was floating point you would result in having 15.2. Then 15 / 10 = 1. So we've got idea for removing from the right, now let's think about the left side.
And here comes modulo - to rescue us! Let's have 152 as example once again. 152 modulo 100 = 52, equivalent to removing the first number. Then 152 % 10 = 2 and operation is completed. It's very helpful to remember these tricks as they may come handy in the most unexpected moments.
See how we finished all smaller problems? Now it's time to connect them all together in the main function.
As we know that there's only eleven primes we can only iterate the loop eleven times. If the number is truncatable we will print it's value and we'll add it to the sum of all truncatable primes.
Remember about essential libraries - cmath and iostream, and we're ready to go.
Great - it works and in addition it works quite fast so I'm happy with this result. As you probably know you can try to approach this problem in different ways so don't worry if you came up with something different and/or better. For more project euler challenges check out my GitHub W3ndige
As a sidenote I would like to apologize for the smaller amount of content - I lack free time as I'm concentrating on programming and mathematics to pass my exams, but don't worry - I'm working on a few netsec connected posts and projects so keep tuned for more!