C++如何判断一个整数是否为超级素数-C++-PHP中文网

超级素数指本身是素数且其在素数序列中的下标（从1开始）也是素数；32位整数范围内超级素数不足1000个，宜预生成查表而非在线计算。

c++如何判断一个整数是否为超级素数

什么是超级素数，为什么不能直接筛到10⁹

超级素数指本身是素数，且它在素数序列中的下标（从1开始计数）也是素数。例如第2个素数是3，2是素数 → 3是超级素数；第3个素数是5，3是素数 → 5也是；但第4个素数是7，4不是素数 → 7不是超级素数。

关键限制在于：第n个素数约等于 n·ln(n)，而第10⁶个素数已超1.5×10⁷，所以若要判断一个int范围内的数（最大约2.1×10⁹）是否为超级素数，最多只需知道前约5×10⁷个素数——但这不现实。实际中，**所有32位有符号整数范围内的超级素数只有不到1000个**，穷举预生成更高效。

如何用埃氏筛 + 索引映射快速查表

先筛出足够多的素数（比如前20000个），再从中挑出“下标为素数”的那些，存入std::unordered_set或排序数组。查一个数时直接count()或二分查找。

C++ Code Review Master

组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。

下载

筛够前N个素数：用动态扩容的vector<bool></bool>筛到约250000即可稳定拿到前20000素数（第20000个素数是224737）
下标从1开始：primes[0]对应第1个素数，所以第k个素数的下标k需单独判断是否为素数
只存超级素数本身：不需要存下标，查的时候只关心输入值是否在集合里

// 示例：生成前1000个超级素数（足够覆盖 int 范围）
vector<int> primes = sieve_to_n_primes(20000); // 埃氏筛得前20000素数
vector<int> super_primes;
for (int i = 0; i 

<h3>
<code>is_prime</code>对小整数必须快，但别误用大数逻辑</h3>
<p>判断下标<code>idx</code>（最大约20000）是否为素数，完全不需要Miller-Rabin。用6k±1试除到<code>sqrt(idx)</code>，或直接打表<code>bool small_prime[20001]</code>——后者零开销。</p>
<ul>
<li>错误做法：对每个<code>idx</code>都调用通用大数<code>is_prime</code>，引入不必要的模运算和循环</li>
<li>正确做法：静态初始化一个<code>constexpr array<bool></bool></code>，编译期完成</li>
<li>注意边界：<code>idx=1</code>不是素数，超级素数从第2个素数（即3）开始</li>
</ul>
<h3>查一个<code>int</code>是否为超级素数：别现场算，直接查集合</h3>
<p>运行时判断就是O(1)哈希查找或O(log n)二分，比任何在线素性测试都快。预生成集合后，用户代码极简：</p>
<pre class="brush:php;toolbar:false;">
bool is_super_prime(int n) {
    static const unordered_set<int> sp = build_super_primes();
    return sp.find(n) != sp.end();
}
</int>

容易忽略的一点：int可能为负数或0，这些直接返回false，不必进集合查找。另外，INT_MAX是2147483647，而第1000个超级素数才刚过150万，所以集合大小百来KB，毫无压力。