115 lines
4.6 KiB
C
115 lines
4.6 KiB
C
/* The four adjacent digits in the 1000-digit number that have the greatest product are 9 × 9 × 8 × 9 = 5832.
|
||
*
|
||
* 73167176531330624919225119674426574742355349194934
|
||
* 96983520312774506326239578318016984801869478851843
|
||
* 85861560789112949495459501737958331952853208805511
|
||
* 12540698747158523863050715693290963295227443043557
|
||
* 66896648950445244523161731856403098711121722383113
|
||
* 62229893423380308135336276614282806444486645238749
|
||
* 30358907296290491560440772390713810515859307960866
|
||
* 70172427121883998797908792274921901699720888093776
|
||
* 65727333001053367881220235421809751254540594752243
|
||
* 52584907711670556013604839586446706324415722155397
|
||
* 53697817977846174064955149290862569321978468622482
|
||
* 83972241375657056057490261407972968652414535100474
|
||
* 82166370484403199890008895243450658541227588666881
|
||
* 16427171479924442928230863465674813919123162824586
|
||
* 17866458359124566529476545682848912883142607690042
|
||
* 24219022671055626321111109370544217506941658960408
|
||
* 07198403850962455444362981230987879927244284909188
|
||
* 84580156166097919133875499200524063689912560717606
|
||
* 05886116467109405077541002256983155200055935729725
|
||
* 71636269561882670428252483600823257530420752963450
|
||
*
|
||
* Find the thirteen adjacent digits in the 1000-digit number that have the greatest product. What is the value of this product?*/
|
||
|
||
#define _POSIX_C_SOURCE 199309L
|
||
|
||
#include <stdio.h>
|
||
#include <stdlib.h>
|
||
#include <time.h>
|
||
|
||
int main(int argc, char **argv)
|
||
{
|
||
char string[] = "73167176531330624919225119674426574742355349"
|
||
"19493496983520312774506326239578318016984801"
|
||
"86947885184385861560789112949495459501737958"
|
||
"33195285320880551112540698747158523863050715"
|
||
"69329096329522744304355766896648950445244523"
|
||
"16173185640309871112172238311362229893423380"
|
||
"30813533627661428280644448664523874930358907"
|
||
"29629049156044077239071381051585930796086670"
|
||
"17242712188399879790879227492190169972088809"
|
||
"37766572733300105336788122023542180975125454"
|
||
"05947522435258490771167055601360483958644670"
|
||
"63244157221553975369781797784617406495514929"
|
||
"08625693219784686224828397224137565705605749"
|
||
"02614079729686524145351004748216637048440319"
|
||
"98900088952434506585412275886668811642717147"
|
||
"99244429282308634656748139191231628245861786"
|
||
"64583591245665294765456828489128831426076900"
|
||
"42242190226710556263211111093705442175069416"
|
||
"58960408071984038509624554443629812309878799"
|
||
"27244284909188845801561660979191338754992005"
|
||
"24063689912560717606058861164671094050775410"
|
||
"02256983155200055935729725716362695618826704"
|
||
"28252483600823257530420752963450";
|
||
char cur, out;
|
||
long int max = 0, tmp = 1;
|
||
int i, j;
|
||
double elapsed;
|
||
struct timespec start, end;
|
||
|
||
clock_gettime(CLOCK_MONOTONIC, &start);
|
||
|
||
for(i = 0; i < 1000; i++)
|
||
{
|
||
/* For the first 13 digits, just multiply them.*/
|
||
if(i < 13)
|
||
{
|
||
cur = string[i] - '0';
|
||
tmp *= (long int)cur;
|
||
}
|
||
else
|
||
{
|
||
/* If the current product is greater than the maximum, save the current as maximum.*/
|
||
if(tmp > max)
|
||
{
|
||
max = tmp;
|
||
}
|
||
/* Check the value of the first digit of the previous sequence, which will not be part
|
||
* of the next sequence.*/
|
||
out = string[i-13] - '0';
|
||
/* If the digit is zero, multiply all the 13 digits of the new sequence.*/
|
||
if(out == 0)
|
||
{
|
||
tmp = 1;
|
||
for(j = i - 12; j <= i; j++)
|
||
{
|
||
cur = string[j] - '0';
|
||
tmp *= (long int)cur;
|
||
}
|
||
}
|
||
/* If the digit not zero, instead of multiplying all the 13 digits of the new sequence,
|
||
* divide the current product by the remove digit and multiply it by the new digit.*/
|
||
else
|
||
{
|
||
cur = string[i] - '0';
|
||
tmp /= (long int)out;
|
||
tmp *= (long int)cur;
|
||
}
|
||
}
|
||
}
|
||
|
||
clock_gettime(CLOCK_MONOTONIC, &end);
|
||
|
||
elapsed = (end.tv_sec - start.tv_sec) + (double)(end.tv_nsec - start.tv_nsec) / 1000000000;
|
||
|
||
printf("Project Euler, Problem 8\n");
|
||
printf("Answer: %ld\n", max);
|
||
|
||
printf("Elapsed time: %.9lf seconds\n", elapsed);
|
||
|
||
return 0;
|
||
}
|