86 lines
1.8 KiB
C
86 lines
1.8 KiB
C
/* It is possible to write ten as the sum of primes in exactly five different ways:
|
|
*
|
|
* 7 + 3
|
|
* 5 + 5
|
|
* 5 + 3 + 2
|
|
* 3 + 3 + 2 + 2
|
|
* 2 + 2 + 2 + 2 + 2
|
|
*
|
|
* What is the first value which can be written as the sum of primes in over five thousand different ways?*/
|
|
|
|
#define _POSIX_C_SOURCE 199309L
|
|
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <math.h>
|
|
#include <time.h>
|
|
#include "projecteuler.h"
|
|
|
|
int count(int value, int n, int i, int target);
|
|
|
|
int primes[100];
|
|
|
|
int main(int argc, char **argv)
|
|
{
|
|
int i, j, n;
|
|
double elapsed;
|
|
struct timespec start, end;
|
|
|
|
clock_gettime(CLOCK_MONOTONIC, &start);
|
|
|
|
/* Generate a list of the first 100 primes.*/
|
|
for(i = 0, j = 0; j < 100; i++)
|
|
{
|
|
if(is_prime(i))
|
|
{
|
|
primes[j++] = i;
|
|
}
|
|
}
|
|
|
|
i = 1;
|
|
|
|
/* Use a function to count the number of prime partitions for
|
|
* each number >= 2 until the one that can be written in over
|
|
* 5000 ways is found.*/
|
|
while((n = count(0, 0, 0, ++i)) <= 5000);
|
|
|
|
clock_gettime(CLOCK_MONOTONIC, &end);
|
|
|
|
elapsed = (end.tv_sec - start.tv_sec) + (double)(end.tv_nsec - start.tv_nsec) / 1000000000;
|
|
|
|
printf("Project Euler, Problem 77\n");
|
|
printf("Answer: %d\n", i);
|
|
|
|
printf("Elapsed time: %.9lf seconds\n", elapsed);
|
|
|
|
return 0;
|
|
}
|
|
|
|
/* Function using a simple recursive brute force approach
|
|
* to find all the partitions.*/
|
|
int count(int value, int n, int i, int target)
|
|
{
|
|
int j;
|
|
|
|
for(j = i; j < 100; j++)
|
|
{
|
|
value += primes[j];
|
|
|
|
if(value == target)
|
|
{
|
|
return n + 1;
|
|
}
|
|
else if(value > target)
|
|
{
|
|
return n;
|
|
}
|
|
else
|
|
{
|
|
n = count(value, n, j, target);
|
|
value -= primes[j];
|
|
}
|
|
}
|
|
|
|
return n;
|
|
}
|