This problem is from project Euler problem 4. I am a beginner in programming and I only understand data types, variables, loops ,arrays and functions. if the answer turns out to be really complicated please tell me what to look up.
So the problem was: A palindromic number reads the same both ways. The largest palindrome made from the product of two 2 -digit numbers is 9009=91*99.
Find the largest palindrome made from the product of two 3-digit numbers.
The difficulty of this problem is apparently easy but It took me days. The original program I designed had some syntax errors so I used some help from chat-gpt.
#include <stdio.h>
#include <stdbool.h>
// palindrome checker
bool is_palindrome(int p) {
int original = p;
int reversed = 0;
int remainder;
// Reverse the digits
while (p > 0) {
remainder = p % 10;
reversed = reversed * 10 + remainder;
p = p / 10;
}
// Check if the original number is the same as the reversed number
//turns out I don't have to say if original == reversed , return true.
return original == reversed;
}
int main(void) {
int largest_palindrome = 0;
int factor1 = 0, factor2 = 0;
// Check products of all pairs of 3-digit numbers
for (int i = 10000; i <= 99999; i++) {
for (int j = 10000; j <= 99999; j++) {
int product = i * j;
if (is_palindrome(product) && product > largest_palindrome) {
largest_palindrome = product;
factor1 = i;
printf("Factor 1 : %d\n",i);//I wanted to see the patterns of the factors
factor2 = j;
printf("Factor 2 : %d\n",j);
printf(" product : %d\n",largest_palindrome);
}
}
}
printf("The largest palindrome made from the product of two 5-digit numbers is %d (%d * %d).\n", largest_palindrome, factor1, factor2);
return 0;
}*/
bool is_palindrome(int p) {
int original = p;
int reversed = 0;
int remainder;
while (p > 0) {
remainder = p % 10;
reversed = reversed * 10 + remainder;
p = p / 10;
}
return original == reversed;
}
int main(void) {
int largest_palindrome = 0;
int factor1 = 0, factor2 = 0;
//my genius idea
for (int i = 99999; i >= 10000; i--) {
for (int j =99999; j >= 10000; j--) {
int product = i * j;
// If the product is less than the largest palindrome yet, break loop
if (product <= largest_palindrome) {
break;
}
if (is_palindrome(product)) {
factor1 = i;
printf("Factor 1 : %d\n",i);
factor2 = j;
printf("Factor 2 : %d\n",j);
largest_palindrome = product;
printf(" product : %d\n",largest_palindrome);
}
}
}
printf("The largest palindrome made from the product of two 5-digit numbers is %d (%d * %d).\n", largest_palindrome, factor1, factor2);
return 0;
}
1st program gave the right result for 3 digit numbers ,906609(993*991) which is. Took 45ms on an online compiler. 4 digit took 1 second or something like that. 99000099 (9999 * 9901). For 5 digits it took a minute. 2147447412 (21516 * 99807) One factor seems to be a lot smaller than the other, I found that somewhat interesting.
9999999999 =9999800001. and 1000010000=100000000 so checking the factors from the upper limit and going i--,j-- should be a lot faster.
for the 2nd program the result is 2126776212 (21397 * 99396).took less than a second which is cool but the answer didn't match. After inspecting the printf's i saw that it was going in the right direction,2126776212 (21397 * 99396) is 3 palindromes behind 2147447412 (21516 * 99807) which is the result of the first one. for 3 and 4 digit pair of factors both programs give the same result.
Now I don't know if one of them is correct or both are wrong. I don't think i can look it up using some online calculator.
please tell me what you think. Thank you.
As others have pointed out, you're likely overflowing int with your 10-digit products, which is breaking your results. For both capacity and performance, all of your integral variables should be unsigned long.
Your approach in the second example is good, but there are also a couple of optimizations you can add to speed things up:
#include <stdio.h>
static int is_palindrome(unsigned long p)
{
unsigned long reversed = 0;
unsigned long original = p;
while (p)
{
// (1)
unsigned long remainder = p % 10;
p /= 10;
reversed = (reversed * 10) + remainder;
}
return original == reversed;
}
int main()
{
unsigned long largest_palindrome = 0;
unsigned long factor1, factor2;
for (unsigned long i = 99999; i >= 10000; --i)
{
// (2)
for (unsigned long j = i; j >= 10000; --j)
{
unsigned long product = i * j;
// If the product is less than the largest palindrome yet, break loop
if (product <= largest_palindrome)
break;
if (is_palindrome(product))
{
largest_palindrome = product;
factor1 = i;
factor2 = j;
printf("\t%lu\t%lu\t%lu\n", factor1, factor2, product);
}
}
}
printf("largest = %lu\n", largest_palindrome);
return 0;
}
The change in is_palindrome makes the operation a bit faster because the CPU calculates the result and remainder of a division in a single instruction.
j never needs to be greater than i because that combination must have already been checked.