' Puzzlet #048
' To find all 4-digit primes which remain
' prime for all left and right truncations.
' The truncations of, say, 2397 produce
' all of the following:
' 2, 7, 23, 97, 239, 397.
' Don't forget - 1 isn't a prime number,
' but 2 is!
' By Dave Ellis.
declare IsPrime(p: int)
declare AllTruncationsPrime(p: int)
declare PrintResult(p: int)
def num: int
openconsole
print "Searching ...": print
num = 1001
do
if IsPrime(num)
if AllTruncationsPrime(num)
PrintResult(num)
endif
endif
num = num + 2
until num > 9997
print: print "No more!"
print: print "Press a key to exit ... ",
do: until inkey$ <> ""
closeconsole
end
sub IsPrime(p)
' if p is prime, returns 1,
' otherwise returns 0
def flag, i, root: int
if p = 2 | p = 3
flag = 1
else
if p % 2 = 0 | p < 2
flag = 0
else
root = sqrt(p)
i = 3
flag = 1
do
if p % i = 0
flag = 0
else
i = i + 2
endif
until flag = 0 | i > root
endif
endif
return flag
sub AllTruncationsPrime(p)
' p is prime. If all its left and
' right truncations are also prime,
' returns 1, otherwise returns 0.
def flag, i, temp: int
def p$: string
p$ = ltrim$(str$(p))
flag = 1
i = 1
do
temp = val(left$(p$, i))
if IsPrime(temp)
' do nothing
else
flag = 0
endif
if flag
temp = val(right$(p$, i))
if IsPrime(temp)
' do nothing
else
flag = 0
endif
endif
i = i + 1
until flag = 0 | i > 3
return flag
sub PrintResult(p)
' pretty printer
def p$: string
def i: int
print p, "--> ",
p$ = ltrim$(str$(p))
for i = 1 to 3
print left$(p$, i), " ",
print right$(p$, i), " ",
next i
return
PROGRAM NOTES
In order to simplify these notes, I've given the main routine line numbers. As you can see, using the top-down approach, the whole program is effectively encapsuated in these nine lines.
Line 1: Sets the lowest part of the search range to 1,001. Variable num will hold this value and serve as iterator.
1
2
3
4
5
6
7
8
9
num = 1001
do
if IsPrime(num)
if AllTruncationsPrime(num)
PrintResult(num)
endif
endif
num = num + 2
until num > 9997
Line 2: Opens the main DO loop.
Line 3: Checks that current value of num is a prime number by passing it as the argument to function IsPirme().
Line 4: This line is only executed if the current value of num is a prime number, proven by line 3. It passes num to the function AllTruncationsPrime().
Line 5: This line is only executed if the current value num remains prime for all possible truncations, proven by line 4. It invokes subroutine PrintResult(), whose job is simply to provide a neatly laid-out screen print.
Lines 6 - 8: These close the endifs and increment num. Notice that num is incremented by two. If it were incremented by one, it would be an even number, and even numbers are never prime, defeating the object of the search.
Line 9: checks the latest value of num. If it's still four digits, the program loops around again. If not, the loop is exited and the program halted.
Function IsPrime() has been used in many previous Puzzlets, so doesn't need a description here.
Function AllTruncationsPrime() uses iterator i within a DO loop to inspect all the truncations of p (the local variable name for num). By employing IBasic's built-in string slicing functions, left$ and right$, the left and substrings are extracted. When i is one, these are digits 1 and 4 respectively. When i is 2, these are digit pairs 12 and 34. When i is 3, these are the digit triplets 123 and 234.
At each extraction, function IsPrime() is used to check if the extraction is prime. If it is, the process continues. If not, it's halted. Variable flag indicates success or failure as 1 (TRUE) or 0 (FALSE), and this is the value returned to the main routine.
These are the only two solutions.
Searching ...
3137 --> 3 7 31 37 313 137
3797 --> 3 7 37 97 379 797
No more!
Press any key to exit ...
MAIN MENU
DOWNLOAD CODE
ARCHIVES
Site design/maintenance: Dave Ellis E-mail me!
Last Updated: February 22nd, 2004.