LMMP
4.3.0
Lamina High-Precision Arithmetic Library
Toggle main menu visibility
载入中...
搜索中...
未找到
prime_table.h
浏览该文件的文档.
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
#ifndef __LMMP_PRIME_TABLE_H__
24
#define __LMMP_PRIME_TABLE_H__
25
26
#include "
lmmp/numth.h
"
27
#include <math.h>
28
29
typedef
uint64_t
lmmp_bitset_t
;
30
typedef
uint64_t*
lmmp_bitset_p
;
31
32
#define LMMP_BITSET_BITS (64)
33
#define LMMP_BITSET_MASK (0xffffffffffffffffull)
34
#define LMMP_BITSET_BYTES (8)
35
36
#define PRIME_SHORT_TABLE_SIZE 6542
37
38
#define PRIME_SHORT_TABLE_N 0x10000
39
40
extern
const
ushort
prime_short_table
[
PRIME_SHORT_TABLE_SIZE
];
41
42
/**
43
* @brief 根据全局素数表判断一个数是否为素数
44
* @param p 待判断的数
45
* @warning p>1, p%2==1
46
* @note 若 p 超过了当前全局素数表的范围,则返回 -1
47
* @return 1 素数,0 合数,-1 超出质数表范围
48
*/
49
int
lmmp_is_prime_table_
(
uint
p);
50
51
/**
52
* @brief 计算小于等于 n 的素数数量
53
* @param n 范围
54
* @return 素数数量
55
*/
56
ushort
lmmp_prime_cnt16_
(
ushort
n
);
57
58
/**
59
* @brief 估计 n 范围内的素数数量
60
* @param n 范围
61
* @note 不会低估素数数量,可能恰好超过 pi(n),用以估计素数数组需要的空间
62
* @return 素数数量
63
*/
64
static
inline
ulong
lmmp_prime_size_
(
ulong
n
) {
65
if
(
n
<
PRIME_SHORT_TABLE_N
) {
66
return
lmmp_prime_cnt16_
(
n
);
67
}
else
if
(
n
< 95000) {
68
return
(
ulong
)ceil((
double
)
n
/ (log(
n
) - 1.095)) + 1;
69
}
else
if
(
n
< 355991) {
70
return
(
ulong
)ceil((
double
)
n
/ (log(
n
) - 1.0975)) + 1;
71
}
else
if
(
n
< 1332479531) {
72
// Dusart 2000 估计 - π(x)的上界
73
// lmmp_debug_assert(n >= 355991);
74
double
x = (double)
n
;
75
double
lnx = log(x);
76
double
lnx2 = lnx * lnx;
77
double
r = x / lnx * (1.0 + 1.0 / lnx + 2.51 / lnx2);
78
return
(
ulong
)r;
79
}
80
/*
81
Dusart 2010 估计 - π(x)的严格上界
82
from: Dusart (2010) "Estimates of some functions over primes without R.H."(https://arxiv.org/abs/1002.0442)
83
U(x) = x / [lnx
84
- 1
85
- 1/lnx
86
- 3.35/(lnx)^2
87
- 12.65/(lnx)^3
88
- 71.7/(lnx)^4
89
- 466.1275/(lnx)^5
90
- 3489.8225/(lnx)^6]
91
*/
92
// lmmp_debug_assert(n >= 1332479531);
93
double
lnx = log(
n
);
94
double
lnx2 = lnx * lnx;
95
double
lnx3 = lnx2 * lnx;
96
double
lnx4 = lnx3 * lnx;
97
double
lnx5 = lnx4 * lnx;
98
double
lnx6 = lnx5 * lnx;
99
100
double
denom =
101
lnx - 1.0 - 1.0 / lnx - 3.35 / lnx2 - 12.65 / lnx3 - 71.7 / lnx4 - 466.1275 / lnx5 - 3489.8225 / lnx6;
102
103
return
(
ulong
)ceil(
n
/ denom);
104
}
105
106
/**
107
* @brief 初始化全局素数表
108
* @param n 素数表大小(含n)
109
* @warning 会自动扩容,可以重入;当 n < PRIME_SHORT_TABLE_N 时,将会直接返回
110
* @note mod-30 轮位图存储:每字节存 30 个数中与 30 互素的 8 个候选
111
* (密度 4/15 bit/数,为奇数编码的 8/15),3、5 及其倍数结构性不入位图
112
*/
113
void
lmmp_prime_int_table_init_
(
uint
n
);
114
115
/**
116
* @brief 释放全局素数表
117
*/
118
void
lmmp_prime_int_table_free_
(
void
);
119
120
typedef
struct
{
121
uintp
restrict
pp
;
// 质数数组(升序排列)
122
uint
size
;
// pp 数组大小
123
uint
start_idx
;
// 位图下一次解析的起始索引(字)
124
uint
end_idx
;
// 位图应该终止解析的结束索引(字)
125
uint
end_num
;
// 终止解析的最大数
126
int
is_end
;
// 是否已经遍历到全局质数表末尾
127
}
prime_cache_t
;
128
129
/*
130
示例代码(遍历全局奇素数表):
131
132
lmmp_prime_int_table_init_(n);
133
prime_cache_t cache;
134
lmmp_prime_cache_init_(&cache, n);
135
while (cache.is_end == 0) {
136
lmmp_prime_cache_next_(&cache);
137
for (uint i = 0; i < cache.size; i++) {
138
....
139
}
140
}
141
lmmp_prime_cache_free_(&cache);
142
*/
143
144
/**
145
* @brief 初始化素数表缓存
146
* @param cache 缓存结构体
147
* @param n 遍历素数表的范围(超过n时或者遍历到全局质数表末尾,is_end 置为 1)
148
*/
149
void
lmmp_prime_cache_init_
(
prime_cache_t
* cache,
uint
n
);
150
151
/**
152
* @brief 素数表缓存更新(从小到大遍历全局质数表)
153
* @param cache 缓存结构体
154
* @note 缓存只存储奇素数;3、5 不在 mod-30 位图内,首次解码时补入。
155
* 当遍历到全局质数表末尾或者达到设置的范围时,is_end 置为 1
156
*/
157
void
lmmp_prime_cache_next_
(
prime_cache_t
* cache);
158
159
/**
160
* @brief 释放素数表缓存
161
* @param cache 缓存结构体
162
*/
163
void
lmmp_prime_cache_free_
(
prime_cache_t
* cache);
164
165
#endif
// __LMMP_PRIME_TABLE_H__
n
#define n
numth.h
uint
uint32_t uint
定义
numth.h:38
uintp
uint32_t * uintp
定义
numth.h:46
ushort
uint16_t ushort
定义
numth.h:36
ulong
uint64_t ulong
定义
numth.h:39
lmmp_bitset_t
uint64_t lmmp_bitset_t
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
prime_table.h:29
prime_cache_t::start_idx
uint start_idx
定义
prime_table.h:123
lmmp_prime_cache_free_
void lmmp_prime_cache_free_(prime_cache_t *cache)
释放素数表缓存
定义
prime_sieve.c:363
PRIME_SHORT_TABLE_SIZE
#define PRIME_SHORT_TABLE_SIZE
定义
prime_table.h:36
lmmp_prime_cache_next_
void lmmp_prime_cache_next_(prime_cache_t *cache)
素数表缓存更新(从小到大遍历全局质数表)
定义
prime_sieve.c:302
prime_cache_t::is_end
int is_end
定义
prime_table.h:126
prime_cache_t::size
uint size
定义
prime_table.h:122
lmmp_bitset_p
uint64_t * lmmp_bitset_p
定义
prime_table.h:30
lmmp_prime_int_table_free_
void lmmp_prime_int_table_free_(void)
释放全局素数表
定义
prime_sieve.c:388
prime_cache_t::pp
uintp restrict pp
定义
prime_table.h:121
prime_cache_t::end_idx
uint end_idx
定义
prime_table.h:124
lmmp_prime_size_
static ulong lmmp_prime_size_(ulong n)
估计 n 范围内的素数数量
定义
prime_table.h:64
lmmp_is_prime_table_
int lmmp_is_prime_table_(uint p)
根据全局素数表判断一个数是否为素数
定义
prime_sieve.c:264
PRIME_SHORT_TABLE_N
#define PRIME_SHORT_TABLE_N
定义
prime_table.h:38
prime_short_table
const ushort prime_short_table[6542]
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
prime_table.c:30
lmmp_prime_int_table_init_
void lmmp_prime_int_table_init_(uint n)
初始化全局素数表
定义
prime_sieve.c:123
prime_cache_t::end_num
uint end_num
定义
prime_table.h:125
lmmp_prime_cnt16_
ushort lmmp_prime_cnt16_(ushort n)
计算小于等于 n 的素数数量
定义
prime_sieve.c:368
lmmp_prime_cache_init_
void lmmp_prime_cache_init_(prime_cache_t *cache, uint n)
初始化素数表缓存
定义
prime_sieve.c:284
prime_cache_t
定义
prime_table.h:120
restrict
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)
定义
test_powmod.c:35
src
lmmp
impl
prime_table.h
生成于
, 为 LMMP使用
1.18.0