Efficiency Problem

[Omnipotence]

I was at the DWITE programming contest and I am still mulling over the fifth question in which you must read a lowerint and an upperint and find all the prime palindromes (palindrome being something you could read forward and backward and still be the same) within them. We had to do 5 sets of these in under 2.5 seconds and I am unable to make it efficient enough to do that.

(Working under the assumption that at least 3 of the 5 have to look through at least 100 000 numbers)

So far my code looks like this:

Quote:

var lowerint, upperint, file, counter : int
var counter2, counter3 : int := 0
var line1, line2 : string

open : file, "Input.txt", get

for r : 1 .. 5
get : file, line1
get : file, line2, skip
lowerint := strint (line1)
upperint := strint (line2)
counter2 := 0

for x : lowerint .. upperint
counter := 0
counter3 := 0

for y : 1 .. length (intstr (x))
if intstr (x) (y) not= intstr (x) (length (intstr (x)) - y + 1)
then
exit
else
counter := counter + 1
end if
end for

if counter = length (intstr (x))
then

for z : 2 .. ceil (x / 2)
if x mod z = 0
then
counter3 := counter3 + 1
exit
end if
end for

if counter3 = 0
then
counter2 := counter2 + 1
end if
end if
end for

put counter2
end for

put Time.Elapsed

Mind you, Im using put at the end and Time.Elapsed to check my time and answer. (It reads from file at beginning so Time.Elapsed would work more accurately)

[Cervantes]

Build an array of primes global to each problem set. Increase it when a set requires you to go higher than your current array.