81 lines
1.8 KiB
C
81 lines
1.8 KiB
C
/* Consider the divisors of 30: 1,2,3,5,6,10,15,30.
|
|
* It can be seen that for every divisor d of 30, d+30/d is prime.
|
|
*
|
|
* Find the sum of all positive integers n not exceeding 100 000 000
|
|
* such that for every divisor d of n, d+n/d is prime.*/
|
|
|
|
#define _POSIX_C_SOURCE 199309L
|
|
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <math.h>
|
|
#include <time.h>
|
|
#include "projecteuler.h"
|
|
|
|
#define N 100000000
|
|
|
|
int check_d_nd_prime(int n);
|
|
|
|
int *primes;
|
|
|
|
int main(int argc, char **argv)
|
|
{
|
|
int i;
|
|
long int sum = 1;
|
|
double elapsed;
|
|
struct timespec start, end;
|
|
|
|
clock_gettime(CLOCK_MONOTONIC, &start);
|
|
|
|
if((primes = sieve(N+2)) == NULL)
|
|
{
|
|
fprintf(stderr, "Error! Sieve function returned NULL\n");
|
|
return 1;
|
|
}
|
|
|
|
for(i = 2; i <= N; i += 2)
|
|
{
|
|
/* Every number is divisible by 1, so 1+n/1=n+1 must be prime.*/
|
|
if(primes[i+1] && check_d_nd_prime(i))
|
|
{
|
|
sum += i;
|
|
}
|
|
}
|
|
|
|
clock_gettime(CLOCK_MONOTONIC, &end);
|
|
|
|
elapsed = (end.tv_sec - start.tv_sec) + (double)(end.tv_nsec - start.tv_nsec) / 1000000000;
|
|
|
|
printf("Project Euler, Problem 357\n");
|
|
printf("Answer: %ld\n", sum);
|
|
|
|
printf("Elapsed time: %.9lf seconds\n", elapsed);
|
|
|
|
return 0;
|
|
}
|
|
|
|
int check_d_nd_prime(int n)
|
|
{
|
|
int i, limit;
|
|
|
|
/* To get all divisors, it's sufficient to loop up to the square root
|
|
* of the number, because for every divisor d smaller than sqrt(n) n/d
|
|
* is also a divisor larger than sqrt(n).*/
|
|
limit = floor(sqrt(n));
|
|
|
|
for(i = 2; i <= limit; i++)
|
|
{
|
|
if(n % i == 0)
|
|
{
|
|
/* We only need to check the property for i and not n/i.
|
|
* If d=n/i, we would have to check if n/i+n/(n/i)=n/i+i is prime.*/
|
|
if(!primes[i+n/i])
|
|
{
|
|
return 0;
|
|
}
|
|
}
|
|
}
|
|
|
|
return 1;
|
|
}
|