+ 41

# CHALLENGE : TRUNCATABLE PRIMES 💻⌨️🖱️

Truncatable prime is a prime number that when you successively remove digits from one end of the prime, you are left with a new prime number. Examples: 997 is called a left-truncatable prime as the numbers 997, 97, and 7 are all prime. 7393 is a right-truncatable prime as the numbers 7393, 739, 73, and 7 formed by removing digits from its right are also prime. The task is to find the largest left-truncatable and right-truncatable primes less than 1.000.000 No zeroes are allowed in truncatable prime.

25 ответов

+ 25

For example :
https://code.sololearn.com/c17zdi9D81wP/?ref=app

+ 21

//not some different logic😕
//mine initial logic failed ... worst ever logic thinked in the world
https://code.sololearn.com/cYs5Ya0eIDQ0/?ref=app

+ 17

Thamk you @LukArToDo for your interesting challenge!
Here is my try using C++:
https://code.sololearn.com/c83F40F4QiiY/?ref=app

+ 15

**** (It's updated !!) ***
https://code.sololearn.com/cBAl5Z6BL562/?ref=app

+ 13

Thanks to @LukArToDo
https://code.sololearn.com/cZfL32RGCNqj/?ref=app

+ 12

https://code.sololearn.com/cAnygWXudpqC/?ref=app

+ 11

Gives largest left and right truncatable primes less than or equal to input number https://code.sololearn.com/cD3zpw9Sv8B9/?ref=app

+ 9

@LukArTodo : I love this kind of challenges - congrats!
got a simiiar solution like VcC
leftTruncated Prime:
a 2-digit must end with 3 or 7 and has to be a prime
this set is p2
a 3-digit has to end with a p2 and be a prime
this set is p3....
finally this is my prog
https://code.sololearn.com/cWRktOr1RYlU/?ref=app

+ 7

Why go for millions when you can do billions or trillions ? just enter number of digits (6 to answer the question but higher values work up to 12 digits or 1000000000000)
https://code.sololearn.com/caFQAfueLj5s/?ref=app

+ 6

choose r or l for left- or righttruncated primes
righttruncated:
prefix must be a right truncated prime
last digit must be 1,3,7,9 otherwise cant be a prime
prefix *10 + last digit must be a prime
build 2-digit prefix and derive valid 3-digit prefix and derive 4digit prefix...
left truncated:: see other post
https://code.sololearn.com/cF6SPX5Yxlxl

+ 6

I've learned a lot solving this challenge . Especially how to reduce time cost. Thanks everyone.
https://code.sololearn.com/clHC44CsgF5j/?ref=app

+ 5

Using LINQ 😊
https://code.sololearn.com/cJ1wQgV350hc

+ 5

+ 5

+ 5

Also for lefttruncatable Primes there can be done something:
crossSum must never become devisible by 3
So eg the crossSum of a number is 2, next number may not be 4,7,9
So we can shorten runtime
Tried it by a dynamic generator for demonstrazion
https://code.sololearn.com/cvnTZflUFyQx

+ 3

I found an interesting attribute of right-truncated primes:
They may only have digits 1,3,7,9 so far...
additionally:
The sum of digit 7 and digit 1 must be one or two
- Exactly one digit 7 and no digit 1
- One digit 7 and one digit 1
- Two digits 7 and no digit 1
- Two digits 1 and no digit 7
This comes from checking if 3 is a devisor via crosssum
9 and 3 are neutral
7 and 1 mod 3 is 2
so as soon as you have the third digit(1,7) the number is devisible by 3.
With this knowledge I could shorten runtime a bit
https://code.sololearn.com/c7Ud5wbbRwIo

+ 3

####UPDATED#####
After all that 'Time Limit exceeds' finally it is done....
https://code.sololearn.com/cErf0NLJTvcV/?ref=app