LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
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
29typedef uint64_t lmmp_bitset_t;
30typedef 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
41
42/**
43 * @brief 根据全局素数表判断一个数是否为素数
44 * @param p 待判断的数
45 * @warning p>1, p%2==1
46 * @note 若 p 超过了当前全局素数表的范围,则返回 -1
47 * @return 1 素数,0 合数,-1 超出质数表范围
48 */
50
51/**
52 * @brief 计算小于等于 n 的素数数量
53 * @param n 范围
54 * @return 素数数量
55 */
57
58/**
59 * @brief 估计 n 范围内的素数数量
60 * @param n 范围
61 * @note 不会低估素数数量,可能恰好超过 pi(n),用以估计素数数组需要的空间
62 * @return 素数数量
63 */
64static 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 */
114
115/**
116 * @brief 释放全局素数表
117 */
119
120typedef 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; // 是否已经遍历到全局质数表末尾
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 */
150
151/**
152 * @brief 素数表缓存更新(从小到大遍历全局质数表)
153 * @param cache 缓存结构体
154 * @note 缓存只存储奇素数;3、5 不在 mod-30 位图内,首次解码时补入。
155 * 当遍历到全局质数表末尾或者达到设置的范围时,is_end 置为 1
156 */
158
159/**
160 * @brief 释放素数表缓存
161 * @param cache 缓存结构体
162 */
164
165#endif // __LMMP_PRIME_TABLE_H__
#define n
uint32_t uint
定义 numth.h:38
uint32_t * uintp
定义 numth.h:46
uint16_t ushort
定义 numth.h:36
uint64_t ulong
定义 numth.h:39
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
static ulong lmmp_prime_size_(ulong n)
估计 n 范围内的素数数量
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)
初始化素数表缓存
#define restrict
Copyright (C) 2026 HJimmyK (Jericho Knox)