84 lines
2.3 KiB
C
84 lines
2.3 KiB
C
/* Take the number 192 and multiply it by each of 1, 2, and 3:
|
||
*
|
||
* 192 × 1 = 192
|
||
* 192 × 2 = 384
|
||
* 192 × 3 = 576
|
||
*
|
||
* By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)
|
||
*
|
||
* The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated
|
||
* product of 9 and (1,2,3,4,5).
|
||
*
|
||
* What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1?*/
|
||
|
||
#define _POSIX_C_SOURCE 199309L
|
||
|
||
#include <stdio.h>
|
||
#include <stdlib.h>
|
||
#include <time.h>
|
||
#include "projecteuler.h"
|
||
|
||
int main(int argc, char **argv)
|
||
{
|
||
int i, j, tmp;
|
||
long int n, max = 0;
|
||
double elapsed;
|
||
struct timespec start, end;
|
||
|
||
clock_gettime(CLOCK_MONOTONIC, &start);
|
||
|
||
/* A brute force approach is used, starting with 1 and multiplying
|
||
* the number by 1, 2 etc., concatenating the results, checking if
|
||
* it's 1 to 9 pandigital, and going to the next number when the
|
||
* concatenated result is greater than the greatest 9 digit pandigital
|
||
* value. The limit is set to 10000, since 1*10000=10000, 2*10000=20000 and
|
||
* concatenating this two numbers a 10-digit number is obtained.*/
|
||
for(i = 1; i < 10000; i++)
|
||
{
|
||
n = 0;
|
||
j = 1;
|
||
do
|
||
{
|
||
tmp = i * j;
|
||
n += tmp;
|
||
j++;
|
||
|
||
if(n > max && is_pandigital(n, 9))
|
||
{
|
||
max = n;
|
||
}
|
||
if(i * j < 10)
|
||
{
|
||
n *= 10;
|
||
}
|
||
else if(i * j < 100)
|
||
{
|
||
n *= 100;
|
||
}
|
||
else if(i * j < 1000)
|
||
{
|
||
n *= 1000;
|
||
}
|
||
else if(i * j < 10000)
|
||
{
|
||
n *= 10000;
|
||
}
|
||
else if(i * j < 100000)
|
||
{
|
||
n *= 100000;
|
||
}
|
||
} while(n <= 987654321);
|
||
}
|
||
|
||
clock_gettime(CLOCK_MONOTONIC, &end);
|
||
|
||
elapsed = (end.tv_sec - start.tv_sec) + (double)(end.tv_nsec - start.tv_nsec) / 1000000000;
|
||
|
||
printf("Project Euler, Problem 38\n");
|
||
printf("Answer: %ld\n", max);
|
||
|
||
printf("Elapsed time: %.9lf seconds\n", elapsed);
|
||
|
||
return 0;
|
||
}
|