Project Euler programming challenges: Am I missing something?

[D H]

Right now I'm figuring out a non-brute-force way. Here's pure brute:

When you apply brute force you need to ensure that you are apply that brute force to the right problem. Here you are applying brute force to solve the wrong problem. Your algorithm finds the largest palindrome that is smaller than 999*999=998001. You are not finding the largest palindrome that is the product of two three digit numbers, which is 993*913=906609.

Your program's output is 997799. This has a rather easy factorization: It is product of two primes, 11 and 90709. Since both are prime and neither is a three digit number, this does not qualify as the answer to the problem. Here are two different approaches to the problem:

• Use a double loop that walks through all pairs of three digit numbers. Compute their product. Save the product as the largest palindromic product if the product is larger than your largest palindromic product and if it's a palindrome.
  
  
• Walk downward through the palindromic numbers, starting at 999999 (or 997799 to be a bit smarter). (You'll need an algorithm to form the next smallest palindromic number.) Compute the prime factorization (including repetitions) of the current palindromic number. Stop when the prime factorization can be recombined to form a pair of three digit numbers.

The first approach is a bit more brute forcish, but it's probably going to be faster than the second because factorization is a slow algorithm, as is the recombination of these prime factors.

 

[Jamin2112]

When you apply brute force you need to ensure that you are apply that brute force to the right problem. Here you are applying brute force to solve the wrong problem. Your algorithm finds the largest palindrome that is smaller than 999*999=998001. You are not finding the largest palindrome that is the product of two three digit numbers, which is 993*913=906609.

Your program's output is 997799. This has a rather easy factorization: It is product of two primes, 11 and 90709. Since both are prime and neither is a three digit number, this does not qualify as the answer to the problem. Here are two different approaches to the problem:

• Use a double loop that walks through all pairs of three digit numbers. Compute their product. Save the product as the largest palindromic product if the product is larger than your largest palindromic product and if it's a palindrome.
  
  
• Walk downward through the palindromic numbers, starting at 999999 (or 997799 to be a bit smarter). (You'll need an algorithm to form the next smallest palindromic number.) Compute the prime factorization (including repetitions) of the current palindromic number. Stop when the prime factorization can be recombined to form a pair of three digit numbers.

The first approach is a bit more brute forcish, but it's probably going to be faster than the second because factorization is a slow algorithm, as is the recombination of these prime factors.

Whoops. I can't believe how much of an idiot I am sometimes.