使用内插素数计数函数“pi(x)”值的 table 作为素数数组的上限是否正确？
Is it correct to use a table of interpolated prime-counting function `pi(x)` values as an upper bound for an array of primes?
假设我想分配一个整数数组来存储所有小于N的素数。然后我需要估计数组大小，E(N)。有一个数学函数可以给出 N 以下素数的确切数量，它是 Prime-counting function - pi(n)。然而，用初等函数来定义函数似乎是不可能的。
函数存在一些近似值，但它们都是渐近近似值，因此它们可以高于或低于真实素数，一般不能用作估计值E(N)。
我尝试使用 pi(n) 的表格值来表示某些 n，例如二次方并在它们之间进行插值。但是我注意到函数 pi(n) 是凸函数，因此稀疏 table 点之间的插值可能会意外产生低于真 pi(n) 的 E(n) 值，这可能会导致缓冲区溢出。
然后我决定利用 pi(n) 的单调性质，并使用 pi(2^(n+1)) 的 table 值作为 E(2^n) 的远高于估计值，在它们之间进行插值时间。
我仍然不完全确定对于某些 2^n < X < 2^(n+1) pi(2^(n+1)) 和 pi(2^(n+2)) 之间的插值将是安全的上限估计。这是正确的吗？如何证明？
你想多了。在 C 中，您只需使用 malloc 和 realloc。我愿意 100 次更喜欢一种明显有效的算法，而不是需要深入数学证明的算法。
使用上限。有许多可供选择的数字，每一个都更复杂但更严格。我称此为 prime_count_upper(n)，因为您希望一个值保证大于或等于 n 下的素数个数。参见 Chebyshev、Rosser 和 Schoenfeld、Dusart 1999、Dusart 2010、Axler 2014 和 Büthe 2015。R&S 很简单但并不可怕：π(x) <= x/(log(x)-3/2) for x >= 67 但 Dusart 给出的值越大越好。无论哪种方式，都不需要表格或原始研究。
素数定理保证第n个素数P(n)在n[=范围内28=] log n < P(n) < n log n + n log log n for n > 5. 正如 DanaJ 所建议的，更严格的界限可以计算。
如果你想把质数存储在一个数组中，你不能谈论太大的东西。正如您所建议的，就初等算术函数而言，没有直接计算 pi(n) ，但是有几种计算 pi(n) 这并不难，只要 n 不是太大。例如，参见 this。
假设我想分配一个整数数组来存储所有小于N的素数。然后我需要估计数组大小，E(N)。有一个数学函数可以给出 N 以下素数的确切数量，它是 Prime-counting function - pi(n)。然而，用初等函数来定义函数似乎是不可能的。
函数存在一些近似值，但它们都是渐近近似值，因此它们可以高于或低于真实素数，一般不能用作估计值E(N)。
我尝试使用 pi(n) 的表格值来表示某些 n，例如二次方并在它们之间进行插值。但是我注意到函数 pi(n) 是凸函数，因此稀疏 table 点之间的插值可能会意外产生低于真 pi(n) 的 E(n) 值，这可能会导致缓冲区溢出。
然后我决定利用 pi(n) 的单调性质，并使用 pi(2^(n+1)) 的 table 值作为 E(2^n) 的远高于估计值，在它们之间进行插值时间。
我仍然不完全确定对于某些 2^n < X < 2^(n+1) pi(2^(n+1)) 和 pi(2^(n+2)) 之间的插值将是安全的上限估计。这是正确的吗？如何证明？
你想多了。在 C 中，您只需使用 malloc 和 realloc。我愿意 100 次更喜欢一种明显有效的算法，而不是需要深入数学证明的算法。
使用上限。有许多可供选择的数字，每一个都更复杂但更严格。我称此为 prime_count_upper(n)，因为您希望一个值保证大于或等于 n 下的素数个数。参见 Chebyshev、Rosser 和 Schoenfeld、Dusart 1999、Dusart 2010、Axler 2014 和 Büthe 2015。R&S 很简单但并不可怕：π(x) <= x/(log(x)-3/2) for x >= 67 但 Dusart 给出的值越大越好。无论哪种方式，都不需要表格或原始研究。
素数定理保证第n个素数P(n)在n[=范围内28=] log n < P(n) < n log n + n log log n for n > 5. 正如 DanaJ 所建议的，更严格的界限可以计算。
如果你想把质数存储在一个数组中，你不能谈论太大的东西。正如您所建议的，就初等算术函数而言，没有直接计算 pi(n) ，但是有几种计算 pi(n) 这并不难，只要 n 不是太大。例如，参见 this。