Finding He Largest Palindromic Number, Which Is The Product Of Two Simple (prime) Five-digit Numbers. Javascript

I was trying to write a program that returns the largest palindromic number, which is the product of two simple five-digit numbers, and returns the factors themselves. A prime numb

Solution 1:

Look this link for time-complexity of algorithms. Also this to see how time-complexity can influence to your program efficiency.

This part is not very precise but it can help. Your first loop runs 99999-10000 time. Also this holds for second loop. The isPrime in the worst case runs (99999). So if (i%k===0 && i!==k) return false; runs total_ops = (99999-10000)^2*(99999) times(we skip other part of your code). If your program written in c++ which is more faster than java-script it can run about 2*(10^8)simple operation per second. Your program run time is about(obviously more than) total_ops/(2*10^8) (I suggest calculate it to have an estimation...).

PS: You can put print to your functions to ensure about their progress...

Solution 2:

Problem:: Time Complexity

improvements

1. isPrime()

   function isPrime(n)
   {
       // Corner casesif (n <= 1)  returnfalse;
       if (n <= 3)  returntrue;
   
       // This is checked so that we can skip // middle five numbers in below loopif (n%2 == 0 || n%3 == 0) returnfalse;
   
       for (var i=5; i*i<=n; i=i+6)
           if (n%i == 0 || n%(i+2) == 0)
              returnfalse;
   
       returntrue;
   }
   

   you isprime function is not optimized one. You should use this.

2. Don't find every prime number 2 times.! Just find all prime numbers once, store them into a list, and then pick every number from prime list and check if it is palindrome.

   var primelist = [];
   for(var i = 99999; i > 10000; i++)
   {
        if(isprime(i))
        {
             primelist.push(i);
        }
   }
   for (var i = 0; i < primelist.length; i++) {
       for (var j = 0; j < primelist.length; j++) 
       {
            if(isPalindrome(i*j))
            {
                // Number you want.return (i*j);
            }
       }  
   }
   

3. to check , start from the largest prime numbers.

4. a 5 digit number starts from 10000 to 99999 instead of 11111 to 99999. Although, It does not change the output of the function.