假设我想分配一个整数数组来存储小于某个N的所有素数。然后我需要估计数组大小，E(N) .有一个数学函数给出了 N 以下素数的确切数量，它是素数计数函数 - pi(n) 。但是，根据基本函数来定义函数似乎是不可能的。
函数存在一些近似值，但它们都是渐近近似值，因此它们可以高于或低于素数的真实数，并且通常不能用作估计E(N)。
我尝试将pi(n)的表格值用于某些n，例如二的幂，并在它们之间进行插值。但是，我注意到函数pi(n)是凸的，因此稀疏表点之间的插值可能会意外产生低于真pi(n) E(n)的值，从而导致缓冲区溢出。
然后，我决定利用pi(n)的单调性，并使用pi(2^(n+1))的表值作为这次在它们之间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， and Büthe 2015. R&S很简单，并不可怕：π(x) <= x/(log(x)-3/2) for x >= 67但Dusart为更大的价值提供了更好的价值。 无论哪种方式，都不需要表格或原始研究。
素数定理保证第 n 个素数 P（n） 在 n log n
如果你想将素数存储在数组中，你不能谈论太大的东西。正如你所建议的，就基本算术函数而言，没有直接计算 pi（n） 的方法，但有几种计算 pi（n） 的方法不太难，只要 n 不是太大。例如，看到这个。