117 lines
3.8 KiB
C
117 lines
3.8 KiB
C
/* The primes 3, 7, 109, and 673, are quite remarkable. By taking any two primes and concatenating them in any order the result will always be prime.
|
|
* For example, taking 7 and 109, both 7109 and 1097 are prime. The sum of these four primes, 792, represents the lowest sum for a set of four primes
|
|
* with this property.
|
|
*
|
|
* Find the lowest sum for a set of five primes for which any two primes concatenate to produce another prime.*/
|
|
|
|
#define _POSIX_C_SOURCE 199309L
|
|
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <math.h>
|
|
#include <time.h>
|
|
#include "projecteuler.h"
|
|
|
|
#define N 10000
|
|
|
|
int cat(int i, int j);
|
|
|
|
int *primes;
|
|
|
|
int main(int argc, char **argv)
|
|
{
|
|
int found = 0, p1, p2, p3, p4, p5, n;
|
|
double elapsed;
|
|
struct timespec start, end;
|
|
|
|
clock_gettime(CLOCK_MONOTONIC, &start);
|
|
|
|
if((primes = sieve(N)) == NULL)
|
|
{
|
|
fprintf(stderr, "Error! Sieve function returned NULL\n");
|
|
return 1;
|
|
}
|
|
|
|
/* Straightforward brute force approach.*/
|
|
for(p1 = 3; p1 < N && !found; p1 += 2)
|
|
{
|
|
/* If p1 is not prime, go to the next number.*/
|
|
if(!primes[p1])
|
|
{
|
|
continue;
|
|
}
|
|
|
|
for(p2 = p1 + 2; p2 < N && !found; p2 += 2)
|
|
{
|
|
/* If p2 is not prime, or at least one of the possible concatenations of
|
|
* p1 and p2 is not prime, go to the next number.*/
|
|
if(!primes[p2] || !is_prime(cat(p1, p2)) || !is_prime(cat(p2, p1)))
|
|
{
|
|
continue;
|
|
}
|
|
|
|
for(p3 = p2 + 2; p3 < N && !found; p3 += 2)
|
|
{
|
|
/* If p3 is not prime, or at least one of the possible concatenations of
|
|
* p1, p2 and p3 is not prime, go to the next number.*/
|
|
if(!primes[p3] || !is_prime(cat(p1, p3)) || !is_prime(cat(p3, p1)) ||
|
|
!is_prime(cat(p2, p3)) || !is_prime(cat(p3, p2)))
|
|
{
|
|
continue;
|
|
}
|
|
|
|
for(p4 = p3 + 2; p4 < N && !found; p4 += 2)
|
|
{
|
|
/* If p4 is not prime, or at least one of the possible concatenations of
|
|
* p1, p2, p3 and p4 is not prime, go to the next number.*/
|
|
if(!primes[p4] || !is_prime(cat(p1, p4)) || !is_prime(cat(p4, p1)) ||
|
|
!is_prime(cat(p2, p4)) || !is_prime(cat(p4, p2)) ||
|
|
!is_prime(cat(p3, p4)) || !is_prime(cat(p4, p3)))
|
|
{
|
|
continue;
|
|
}
|
|
|
|
for(p5 = p4 + 2; p5 < N && !found; p5 += 2)
|
|
{
|
|
/* If p5 is not prime, or at least one of the possible concatenations of
|
|
* p1, p2, p3, p4 and p5 is not prime, go to the next number.*/
|
|
if(!primes[p5] || !is_prime(cat(p1, p5)) || !is_prime(cat(p5, p1)) ||
|
|
!is_prime(cat(p2, p5)) || !is_prime(cat(p5, p2)) ||
|
|
!is_prime(cat(p3, p5)) || !is_prime(cat(p5, p3)) ||
|
|
!is_prime(cat(p4, p5)) || !is_prime(cat(p5, p4)))
|
|
{
|
|
continue;
|
|
}
|
|
|
|
/* If it gets here, the five values have been found.*/
|
|
n = p1 + p2 + p3 + p4 + p5;
|
|
found = 1;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
free(primes);
|
|
|
|
clock_gettime(CLOCK_MONOTONIC, &end);
|
|
|
|
elapsed=(end.tv_sec-start.tv_sec)+(double)(end.tv_nsec-start.tv_nsec)/1000000000;
|
|
|
|
printf("Project Euler, Problem 60\n");
|
|
printf("Answer: %d\n", n);
|
|
|
|
printf("Elapsed time: %.9lf seconds\n", elapsed);
|
|
|
|
return 0;
|
|
}
|
|
|
|
int cat(int i, int j)
|
|
{
|
|
char n[10];
|
|
|
|
sprintf(n, "%d%d", i, j);
|
|
|
|
return atoi(n);
|
|
}
|