You are not logged in. Please login at www.codechef.com to post your questions!

×

Prime Palindrome HELP Part 3-Time Exceeded

I've optimized the prime function and its still exceeding the time limit? Any ideas? Solution located at : http://www.codechef.com/viewsolution/3901718

asked 13 May '14, 09:40

tyrthor's gravatar image

0★tyrthor
5210
accept rate: 0%


Your solution is of complexity O(n*sqrt(n)) and n can go up to 10^6, thus your solution exceeds time limit.

Since the number of prime palindromes, less than or equal to 1000000 is not very huge, you can preprocess it on your local machine and use it in your solution. (That has been done by most of the users with fastest execution times for that question).

One optimization that you can try is storing all primes using a sieve and then checking for the palindromes.

link

answered 13 May '14, 10:26

wittyceaser's gravatar image

2★wittyceaser
3.4k194377
accept rate: 16%

Checking prime function takes too much time.

Try checking isprime only if the number is a palindrome.

if(ispalindrome(m))
  if(isprime(m))
    print m
link

answered 13 May '14, 10:39

abbas's gravatar image

4★abbas
4118
accept rate: 28%

Here is your accepted solution http://www.codechef.com/viewsolution/3901791

(13 May '14, 10:51) abbas4★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×3,820
×2,738
×1,918
×266
×195

question asked: 13 May '14, 09:40

question was seen: 1,305 times

last updated: 13 May '14, 10:51