patterncppModerate

Largest palindrome that can be made from a product of 2 3-digit numbers (Project Euler 4)

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

codereview cpp stackoverflow c++palindrome c++11 programming-challenge

canmadenumbersproductlargestpalindromeprojectthatdigiteuler

Problem

This is my solution to Project Euler #4, which asks for the largest palindrome that can be made from a product of 2 3-digit numbers. I have done a brute force method, but it takes around 10-20 seconds to run. It works by looping through 2 variables, finding its product, and converting it to a string to check for palindromity. What steps can I take to improve the computational speed of this program?

#include 
#include 
#include 
#include 
int main()
{
int ans=0;
for(int i=100;ians?ans=num_to_test:ans=ans;
            }
        }
    }
cout > quit;
}

Solution

Speeding things up

There are several things you could do to speed things up:

Instead of looping from 100..999, go from 999..100 instead. That way, if you find a palindrome, you can break from the j loop because any lower values of j will not beat the one you just found.

Once you loop backwards, you can also check ij versus the best answer you've found so far. If ij

You don't have to use log10 to find the number of digits. Since you are already converting the number to a string, just use num_stringstream.length().

The j loop can start at i instead of 999, because any j higher than i will already have been tested.




Cleaning things up

It would make your program look a lot more readable if you moved all of the palindrome checking logic to its own function.

This line here is very hard to read:

num_to_test>ans?ans=num_to_test:ans=ans;


Putting it all together

Here is what I think your code should look like.  I removed the

cin << quit

 part because I wanted to time the program without requiring user input.

#include 
#include 
#include 

bool is_palindrome(int num)
{
    ostringstream convert;
    convert = 100; i--)
    {
        for (int j = i; j >= 100; j--)
        {
            int num_to_test = i * j;

            if (num_to_test <= best)
                break;

            if (is_palindrome(num_to_test)) {
                best = num_to_test;
                break;
            }
        }
    }
    cout << best << endl;
}


Using

gcc -O3`, this program ran in 0.03 seconds on my computer as opposed to 1.06 seconds, for around a 30x speedup.

Code Snippets

num_to_test>ans?ans=num_to_test:ans=ans;

#include <string>
#include <sstream>
#include <iostream>

bool is_palindrome(int num)
{
    ostringstream convert;
    convert << num;
    string num_stringstream = convert.str();
    int num_of_digits = num_stringstream.length();
    for (int i=0; i < num_of_digits; i++)
    {
        if (num_stringstream[i] != num_stringstream[num_of_digits-i-1])
            return false;
    }
    return true;
}

int main(void)
{
    int best = 0;
    for (int i = 999; i >= 100; i--)
    {
        for (int j = i; j >= 100; j--)
        {
            int num_to_test = i * j;

            if (num_to_test <= best)
                break;

            if (is_palindrome(num_to_test)) {
                best = num_to_test;
                break;
            }
        }
    }
    cout << best << endl;
}

Context

StackExchange Code Review Q#101246, answer score: 11

Revisions (0)

No revisions yet.