108 lines
2.5 KiB
C
108 lines
2.5 KiB
C
/* The radical of n, rad(n), is the product of the distinct prime factors of n. For example, 504 = 23 × 32 × 7, so rad(504) = 2 × 3 × 7 = 42.
|
||
*
|
||
* If we calculate rad(n) for 1 ≤ n ≤ 10, then sort them on rad(n), and sorting on n if the radical values are equal, we get:
|
||
*
|
||
* Unsorted Sorted
|
||
* n rad(n) n rad(n) k
|
||
* 1 1 1 1 1
|
||
* 2 2 2 2 2
|
||
* 3 3 4 2 3
|
||
* 4 2 8 2 4
|
||
* 5 5 3 3 5
|
||
* 6 6 9 3 6
|
||
* 7 7 5 5 7
|
||
* 8 2 6 6 8
|
||
* 9 3 7 7 9
|
||
* 10 10 10 10 10
|
||
*
|
||
* Let E(k) be the kth element in the sorted n column; for example, E(4) = 8 and E(6) = 9.
|
||
*
|
||
* If rad(n) is sorted for 1 ≤ n ≤ 100000, find E(10000).*/
|
||
|
||
#define _POSIX_C_SOURCE 199309L
|
||
|
||
#include <stdio.h>
|
||
#include <stdlib.h>
|
||
#include <math.h>
|
||
#include <time.h>
|
||
#include "projecteuler.h"
|
||
|
||
#define N 100000
|
||
|
||
typedef struct n_rad
|
||
{
|
||
int n;
|
||
int radn;
|
||
} n_radn;
|
||
|
||
int compare(void *a, void *b);
|
||
|
||
int main(int argc, char **argv)
|
||
{
|
||
int i, *primes;
|
||
n_radn **rads;
|
||
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;
|
||
}
|
||
|
||
if((rads = (n_radn **)malloc(N*sizeof(n_radn *))) == NULL)
|
||
{
|
||
fprintf(stderr, "Error while allocating memory\n");
|
||
return 1;
|
||
}
|
||
|
||
for(i = 0; i < N; i++)
|
||
{
|
||
if((rads[i] = (n_radn *)malloc(sizeof(n_radn))) == NULL)
|
||
{
|
||
fprintf(stderr, "Error while allocating memory\n");
|
||
return 1;
|
||
}
|
||
}
|
||
|
||
for(i = 0; i < N; i++)
|
||
{
|
||
rads[i]->n = i + 1;
|
||
rads[i]->radn = radical(i+1, primes);
|
||
}
|
||
|
||
free(primes);
|
||
|
||
quick_sort((void **)rads, 0, N-1, compare);
|
||
|
||
clock_gettime(CLOCK_MONOTONIC, &end);
|
||
|
||
elapsed = (end.tv_sec - start.tv_sec) + (double)(end.tv_nsec - start.tv_nsec) / 1000000000;
|
||
|
||
printf("Project Euler, Problem 124\n");
|
||
printf("Answer: %d\n", rads[9999]->n);
|
||
|
||
printf("Elapsed time: %.9lf seconds\n", elapsed);
|
||
|
||
return 0;
|
||
}
|
||
|
||
int compare(void *a, void *b)
|
||
{
|
||
n_radn *rad1, *rad2;
|
||
|
||
rad1 = (n_radn *)a;
|
||
rad2 = (n_radn *)b;
|
||
|
||
if(rad1->radn != rad2->radn)
|
||
{
|
||
return rad1->radn - rad2->radn;
|
||
}
|
||
else
|
||
{
|
||
return rad1->n - rad2->n;
|
||
}
|
||
}
|