LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
prime_sieve.c
浏览该文件的文档.
1/**
2 * Copyright (C) 2026 HJimmyK (Jericho Knox)
3 *
4 * This file is part of LMMP.
5 *
6 * LMMP is free software: you can redistribute it and/or modify it
7 * under the terms of the GNU Lesser General Public License as
8 * published by the Free Software Foundation; either version 3 of
9 * the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library. If not, see
18 * <https://www.gnu.org/licenses/>.
19 *
20 * SPDX-License-Identifier: LGPL-3.0-or-later
21 */
22
23#include "impl/prime_table.h"
24#include "mparam.h"
25#include "impl/inlines.h"
26#include "impl/tmp_alloc.h"
27
28
29typedef struct prime_int {
30 lmmp_bitset_p restrict map; // mod-30 位图(1 为素数,字节 b 位 s 代表数 30b+res8[s])
31 uint map_size; // 位图字容量
32 uint max; // 位图记录的最大值
34
36 .map = NULL,
37 .map_size = 0,
38 .max = 0
39};
40
41#define G global_prime_int_table
42
43/*
44 * mod-30 轮存储:与 30 互素的余数共 8 个(slot 0..7 升序),位图每字节存 30 个
45 * 数中的 8 个候选,密度 4/15 bit/数,为奇数编码(1/2 bit/数)的 8/15,同上限内存
46 * ÷1.875。数与位下标互转(x 为 wheel 数,i 为其位下标):
47 * I(x) = 8*(x/30) + slot30[x%30]
48 * N(i) = 30*(i/8) + res8[i%8]
49 * 3、5 的倍数被结构性排除,不入位图(3、5 本身由遍历端补入)。
50 */
51static const uint res8[8] = {1, 7, 11, 13, 17, 19, 23, 29};
52
53// 余数 -> slot(与 30 非互素为 0xFF)
54static const uchar slot30[30] = {0xFF, 0, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 1, 0xFF, 0xFF, 0xFF, 2, 0xFF, 3, 0xFF, 0xFF,
55 0xFF, 4, 0xFF, 5, 0xFF, 0xFF, 0xFF, 6, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 7};
56
57// 与 30 非互素的余数 -> 到下一个 wheel 数的增量(互素余数为 0)
58static const uchar bump30[30] = {1, 0, 5, 4, 3, 2, 1, 0, 3, 2, 1, 0, 1, 0, 3,
59 2, 1, 0, 1, 0, 3, 2, 1, 0, 5, 4, 3, 2, 1, 0};
60
61// 互素余数 -> 到下一个 wheel 数的差(wheel 数序列的循环间隙 6,4,2,4,2,4,6,2)
62static const uchar gap30[30] = {0, 6, 0, 0, 0, 0, 0, 4, 0, 0, 0, 2, 0, 4, 0,
63 0, 0, 2, 0, 4, 0, 0, 0, 6, 0, 0, 0, 0, 0, 2};
64
65// slot -> res8[slot] 的 mod 30 逆元({7,13}、{17,23} 互换,1/11/19/29 自逆)
66static const uchar inv30_by_slot[8] = {1, 13, 11, 7, 23, 19, 17, 29};
67
68#define WHEEL_IDX(x) (8 * ((x) / 30) + slot30[(x) % 30])
69#define WHEEL_NUM(i) (30 * ((i) >> 3) + res8[(i) & 7])
70#define set_not_prime(p, i) ((p)[(i) >> 3] &= (uchar)~(1u << ((i) & 7)))
71
72// 最大 wheel 数 <= n 的位下标(要求 n >= 3,保证 r==0 时 b >= 1)
73static inline uint wheel_leq_idx(uint n) {
74 uint r = n % 30;
75 uint b = n / 30;
76 if (r == 0)
77 return 8 * b - 1; // 29 属于前一字节
78 while (slot30[r] == 0xFF)
79 --r;
80 return 8 * b + slot30[r];
81}
82
83// 位图字容量:字节数 n/30+1 上取整到字再加一字松弛(容纳尾段整字模式填充)
84static inline uint prime_table_words(uint n) {
85 return (n / 30 + 1) / 8 + 1;
86}
87
88// 分段大小(字)。512KB 恰为目标 L2 容量级,且段容量 2^22 位 >> 最大标记增量
89// (8*(65535*6/30)+8),保证段内每个已启动的质数至少标记数十次,无近空转循环
90#define PRIME_SEG_WORDS (1u << 16)
91
92/*
93 * 7*11 预筛基表:presieve77_table[j] 为绝对字节 j(mod 77)的字节值,清除位恰对应
94 * 7 或 11 的 wheel 倍数(含 7、11 自身,由首次初始化的修正恢复)。7 与 11 在位图
95 * 空间的标记周期为 7/11 字节,故基表为绝对相位周期 77 = 7*11 字节。
96 * 推导规则(可再生成):全 0xFF 起始,对 j in [0,77)、s in [0,8)、x = 30j+res8[s],
97 * x%7==0 或 x%11==0 则清位 s;无任何豁免(b >= 1 的 wheel 倍数全为 >= 49 的真合数,
98 * x=7/11 仅出现在字节 0)。pat[0] = 0xF9:slot1(7)、slot2(11) 清除。
99 */
100static const uchar presieve77_table[77] = {
101 249, 223, 239, 126, 182, 251, 61, 253, 215, 239, 94, 243, 251, 175,
102 253, 158, 239, 124, 247, 243, 191, 221, 219, 239, 110, 247, 186, 191,
103 125, 223, 231, 126, 215, 251, 191, 237, 223, 174, 126, 117, 251, 183,
104 253, 223, 235, 126, 231, 251, 190, 253, 93, 239, 118, 247, 219, 187,
105 253, 207, 239, 62, 247, 121, 191, 245, 223, 207, 122, 247, 235, 191,
106 188, 223, 109, 126, 247, 251, 159};
107
108// 以 pat 周期填充字节 [b0, bend):先铺至多 77 字节种子对齐绝对相位,再倍增 memcpy
109static void fill_pattern(uchar* restrict dst, uint b0, uint bend, const uchar* restrict pat) {
110 uint n = bend - b0;
111 uint seed = n < 77 ? n : 77;
112 for (uint t = 0; t < seed; ++t)
113 dst[b0 + t] = pat[(b0 + t) % 77];
114 for (uint i = b0 + seed; i < bend;) {
115 uint chunk = i - b0;
116 if (chunk > bend - i)
117 chunk = bend - i;
118 memcpy(dst + i, dst + b0, chunk);
119 i += chunk;
120 }
121}
122
125 return;
126
127 uint old_size = G.map_size; // 旧表字数(0 表示首次初始化)
128 uint old_max = G.max;
129 uint new_size = prime_table_words(n);
130
131 if (G.map == NULL) {
132 G.map = ALLOC_TYPE(new_size, lmmp_bitset_t);
133 } else {
134 G.map = REALLOC_TYPE(G.map, new_size, lmmp_bitset_t);
135 }
136 G.map_size = new_size;
137 G.max = n;
138
139 uchar* restrict p = (uchar*)G.map;
140 uint limit_idx = wheel_leq_idx(n); // 有效位上界(含),对应 <= n 的最大 wheel 数
141 uint skip_num = 0, skip_to = 0; // 扩容时旧区域之后的第一个 wheel 数及其位下标
142 if (old_max != 0) {
143 // 宽类型算后继 wheel 数:old_max 贴近 2^32 时 uint 中间量回绕,得到
144 // 失配的 (skip_num,skip_to) 会使重定位标到素数自身(13..29 被清位)
145 ulong sk = (ulong)old_max + 1 + bump30[((ulong)old_max + 1) % 30];
146 if (sk <= MP_UINT_MAX) {
147 skip_num = (uint)sk;
148 skip_to = WHEEL_IDX(skip_num);
149 } else {
150 // uint 域内已无后继 wheel 数,新区域无数可标:MP_UINT_MAX 作域外
151 // 哨兵,重定位 m = p*ceil(UINT_MAX/p) >= UINT_MAX > p^2 恒超 end,
152 // 各素数经既有 idx>=end 路径直接跳过标记(每素数一条除法链)
153 skip_num = MP_UINT_MAX;
154 skip_to = (uint)-1;
155 }
156 }
157
158 ushort sqrt_n = n > 4294836225 ? 0xffff : (ushort)sqrt(n);
159 uint max_idx = lmmp_prime_cnt16_(sqrt_n); // 筛质数个数上界(不含),质数从下标 5(=13)起
160
161 /*
162 * 筛质数状态同块分配(生命周期接力):
163 * next[i]:第 i 个筛质数下一个待清除的全局位下标。保持单调的 p*p 起始
164 * (而非预先跳过旧区域),保证"已启动"质数构成前缀,act 前缀扫描
165 * 才成立;旧区域的跳过在首个段内 O(1) 完成
166 * dslot[s]:标记位落在 slot s 时到下一标记位的位下标增量。标记为
167 * m = p*k(k 跑遍 >= p 的 wheel 数),k 到下一 wheel 数差
168 * g = gap30[k%30],而 k ≡ m*inv(p) (mod 30) 只依赖 m%30 = res8[s]
169 * 与 p,故增量可写成 s 的函数:
170 * dslot[s] = 8*((res8[s]+p*g)/30) + slot30[(res8[s]+p*g)%30] - s
171 * (slot 差为负时由字节进位吸收;含完整 p*g 而非 p%30,故每质数
172 * 现算 8 项而非静态表)。转移 sigma(s) = (s + dslot[s]) & 7 必为
173 * 单一 8 环(k 的余数历经全部 8 个,m = p*k 的余数亦然)。
174 * ds[8i+k]:第 i 个质数的增量按 slot 访问环次序存放;
175 * dpos[8i+s]:slot s 在环中的位置。按环序存放后标记循环展开 8 步取增量
176 * 为常量索引,加载地址可提前计算,打破 idx→load→idx 依赖链
177 * (否则每次标记吃满 load 延迟;旧奇数编码常量步长无此税)。
178 * 跨段/跳过旧区域后由 idx&7 经 dpos 重建环内相位
179 */
180 uchar* restrict blk = ALLOC_TYPE((size_t)max_idx * 44, uchar);
181 uint* restrict next = (uint*)blk;
182 uint* restrict ds = (uint*)(blk + 4 * (size_t)max_idx);
183 uchar* restrict dpos = blk + 36 * (size_t)max_idx;
184 for (uint i = 5; i < max_idx; ++i) {
185 uint prime = prime_short_table[i];
186 next[i] = WHEEL_IDX(prime * prime);
187 uint inv = inv30_by_slot[slot30[prime % 30]];
188 uint dslot[8];
189 for (uint s = 0; s < 8; ++s) {
190 uint d = prime * gap30[(res8[s] * inv) % 30];
191 dslot[s] = 8 * ((res8[s] + d) / 30) + slot30[(res8[s] + d) % 30] - s;
192 }
193 // 自 slot 0 走 sigma 环:ds 按访问次序存放,dpos 记各 slot 的环内位置
194 uint s = 0;
195 for (uint k = 0; k < 8; ++k) {
196 ds[8 * i + k] = dslot[s];
197 dpos[8 * i + s] = (uchar)k;
198 s = (s + dslot[s]) & 7;
199 }
200 }
201
202 uint act = 5; // [5, act) 为已启动的筛质数前缀
203 uint w = old_size;
204 for (;;) {
205 uint wend = w + PRIME_SEG_WORDS;
206 uint last = 0;
207 if (wend >= new_size) {
208 wend = new_size;
209 last = 1;
210 }
211 uint seg_hi = wend * LMMP_BITSET_BITS; // 段结束全局位(不含)
212 uint end = (seg_hi <= limit_idx + 1) ? seg_hi : limit_idx + 1; // 本段标记上界(不含)
213
214 // 段内 7*11 预筛填充(3、5 的倍数由 mod-30 存储结构性排除)。
215 // 扩容增量不足一字时(new_size == old_size)无新字节可填,仅执行标记:
216 // 有效增量位于旧表末字的陈旧 wheel 位上(皆为真合数,标记幂等)
217 fill_pattern(p, w * 8, wend * 8, presieve77_table);
218
219 // p*p 落入界内的质数开始参与(next 单调,构成前缀)
220 while (act < max_idx && next[act] < end)
221 ++act;
222
223 for (uint i = 5; i < act; ++i) {
224 uint prime = prime_short_table[i];
225 uint idx = next[i];
226 if (idx < skip_to) {
227 // 仅首段发生:跳到 >= skip_num 的首个标记 m' = p*k',k' 为
228 // >= ceil(skip_num/p) 的最小 wheel 数(被跳过的 k 满足 p*k < skip_num,
229 // 全在旧区域)。ulong 计算:p*k' 与 skip_num 均可能贴近 2^32
230 ulong k = skip_num / prime + (skip_num % prime != 0);
231 k += bump30[k % 30];
232 ulong m = prime * k;
233 idx = (uint)(8 * (m / 30) + slot30[m % 30]);
234 }
235 if (idx >= end) {
236 // 本段无需标记(仅可能发生在最后一段),保留取整后的 idx
237 next[i] = idx;
238 continue;
239 }
240 const uint* restrict c8 = ds + 8 * i;
241 uint k = dpos[8 * i + (idx & 7)];
242 while (idx < end) {
243 // 环序展开 8 步:增量索引为常量,加载地址提前可算,idx 链只含加法
244 for (uint u = 0; u < 8 && idx < end; ++u, k = (k + 1) & 7) {
245 set_not_prime(p, idx);
246 idx += c8[k];
247 }
248 }
249 next[i] = idx;
250 }
251 if (last)
252 break;
253 w = wend;
254 }
255 lmmp_free(blk);
256
257 if (old_max == 0) {
258 // 首次修正:1 不是素数;7、11 是素数(预筛基表将其自身当倍数抹除)。
259 // 13..29 未被任何 >= 13*13 的标记触碰,自然保留
260 p[0] = 0xFE;
261 }
262}
263
265 if (p < PRIME_SHORT_TABLE_N) {
267 if (prime_short_table[i - 1] == p)
268 return 1;
269 return 0;
270 } else if (p > G.max) {
271 return -1;
272 } else {
273 // p>=3
274 lmmp_param_assert(p > 1);
275 lmmp_param_assert((p & 1) == 1);
276 uint s = slot30[p % 30];
277 if (s == 0xFF)
278 return 0; // p > 65536 且被 3 或 5 整除,必为合数
279 uint idx = 8 * (p / 30) + s;
280 return (int)((((const uchar*)G.map)[idx >> 3] >> (idx & 7)) & 1);
281 }
282}
283
285 lmmp_param_assert(n > 2);
286 lmmp_param_assert(n <= G.max);
288 cache->size = 0;
289 cache->start_idx = 0;
290 cache->end_num = n;
292 cache->is_end = 0;
293}
294
295#define DEC_WORD(m, wbase) \
296 while (m) { \
297 uint t = lmmp_tailing_zeros_(m); \
298 begin[size++] = (uint)((wbase) + 30 * (t >> 3) + res8[t & 7]); \
299 m &= (m - 1); \
300 }
301
303 uint size = 0;
304 ulong idx = cache->start_idx;
305
306 // 3、5 与 30 不互素,不在位图内;首次解码前补入(end_num >= 5 才含 5)
307 if (cache->start_idx == 0) {
308 cache->pp[size++] = 3;
309 if (cache->end_num >= 5)
310 cache->pp[size++] = 5;
311 }
312
313 if (idx + PRIME_CACHE_BLOCK_NUM <= cache->end_idx) {
314 lmmp_bitset_t m0, m1, m2, m3;
315 uintp begin = cache->pp;
316 for (uint i = 0; i < PRIME_CACHE_BLOCK_NUM / 4; ++i) {
317 m0 = G.map[idx + 0];
318 m1 = G.map[idx + 1];
319 m2 = G.map[idx + 2];
320 m3 = G.map[idx + 3];
321 ulong base = idx * 240; // 每字 8 字节 = 240 个数
322 DEC_WORD(m0, base)
323 base += 240;
324 DEC_WORD(m1, base)
325 base += 240;
326 DEC_WORD(m2, base)
327 base += 240;
328 DEC_WORD(m3, base)
329 idx += 4;
330 }
333 cache->start_idx = idx;
334 cache->size = size;
335 return;
336 } else {
337 uint last_off = wheel_leq_idx(cache->end_num) & (LMMP_BITSET_BITS - 1);
338 lmmp_bitset_t last_mask =
339 (last_off == LMMP_BITSET_BITS - 1) ? (lmmp_bitset_t)-1 : (((lmmp_bitset_t)1 << (last_off + 1)) - 1);
341 uintp begin = cache->pp;
342 for (uint i = (uint)idx; i < cache->end_idx; ++i) {
343 m = G.map[i];
344 ulong base = (ulong)i * 240;
345 DEC_WORD(m, base)
346 }
347 m = G.map[cache->end_idx] & last_mask;
348 ulong base = (ulong)cache->end_idx * 240;
349 DEC_WORD(m, base)
351 cache->start_idx = G.map_size;
352 cache->size = size;
353 cache->is_end = 1;
354 return;
355 }
356}
357
358#undef DEC_WORD
359#undef WHEEL_IDX
360#undef WHEEL_NUM
361#undef set_not_prime
362
364 lmmp_free(cache->pp);
365 cache->pp = NULL;
366}
367
369 if (n < 2)
370 return 0;
373
374 ushort lo = 0;
375 ushort hi = PRIME_SHORT_TABLE_SIZE; // [lo, hi)
376
377 while (lo < hi) {
378 ushort mid = lo + (hi - lo) / 2;
379 if (prime_short_table[mid] <= n) {
380 lo = mid + 1;
381 } else {
382 hi = mid;
383 }
384 }
385 return lo;
386}
387
389 lmmp_free(G.map);
390 G.map = NULL;
391 G.max = 0;
392 G.map_size = 0;
393}
#define k
#define MP_UINT_MAX
#define lmmp_debug_assert(x)
定义 lmmp.h:498
void lmmp_free(void *ptr)
内存释放函数(调用lmmp_heap_free_fn)
#define LMMP_THREAD_LOCAL
定义 lmmp.h:114
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define b0
#define t
#define s
#define n
#define lo
#define PRIME_CACHE_SIZE
#define PRIME_CACHE_BLOCK_NUM
uint8_t uchar
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义 numth.h:34
uint32_t uint
定义 numth.h:38
uint32_t * uintp
定义 numth.h:46
uint16_t ushort
定义 numth.h:36
uint64_t ulong
定义 numth.h:39
static const uchar inv30_by_slot[8]
#define PRIME_SEG_WORDS
static LMMP_THREAD_LOCAL prime_int global_prime_int_table
static const uint res8[8]
static uint wheel_leq_idx(uint n)
#define WHEEL_IDX(x)
static const uchar presieve77_table[77]
#define set_not_prime(p, i)
static const uchar bump30[30]
static uint prime_table_words(uint n)
#define DEC_WORD(m, wbase)
static const uchar gap30[30]
#define G
lmmp_bitset_p restrict map
static const uchar slot30[30]
Copyright (C) 2026 HJimmyK (Jericho Knox)
uint64_t lmmp_bitset_t
Copyright (C) 2026 HJimmyK (Jericho Knox)
void lmmp_prime_cache_free_(prime_cache_t *cache)
释放素数表缓存
#define PRIME_SHORT_TABLE_SIZE
void lmmp_prime_cache_next_(prime_cache_t *cache)
素数表缓存更新(从小到大遍历全局质数表)
uint64_t * lmmp_bitset_p
void lmmp_prime_int_table_free_(void)
释放全局素数表
uintp restrict pp
#define LMMP_BITSET_BITS
int lmmp_is_prime_table_(uint p)
根据全局素数表判断一个数是否为素数
#define PRIME_SHORT_TABLE_N
const ushort prime_short_table[6542]
Copyright (C) 2026 HJimmyK (Jericho Knox)
void lmmp_prime_int_table_init_(uint n)
初始化全局素数表
ushort lmmp_prime_cnt16_(ushort n)
计算小于等于 n 的素数数量
void lmmp_prime_cache_init_(prime_cache_t *cache, uint n)
初始化素数表缓存
static void fill_pattern(mp_ptr p, size_t n, mp_limb_t pat)
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
#define REALLOC_TYPE(p, new_size, type)
#define ALLOC_TYPE(n, type)