Computer Science Canada Efficiency Problem |
Author: | Omnipotence [ Sun Feb 26, 2006 12:11 am ] |
Post subject: | 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: 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) |
Author: | Cervantes [ Sun Feb 26, 2006 12:23 am ] |
Post subject: | |
Build an array of primes global to each problem set. Increase it when a set requires you to go higher than your current array. |