-----------------------------------

Omnipotence

Sun Feb 26, 2006 12:11 am


Efficiency Problem

-----------------------------------

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:


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

Sun Feb 26, 2006 12:23 am



-----------------------------------

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