C++质数判断算法的时间测试

野性酷女 2024-03-16 22:53 19阅读 0赞

### 测试标准 ###

这里使用两类、五种常用质数判断**算法**进行测试：枚举因子法（暴力、开方优化、6n再优化）、质数筛（埃氏筛法、欧拉筛法）。（Miller-Rabin呢？不会，没搞懂）

同时，使用两类情况进行测试：

1.  寻找 2-100,000 内的质数个数
2.  寻找 10,000,001-10,009,999 内的质数个数

### 质数判断算法 ###

#### 枚举因子法 ####

##### 1. 暴力遍历 #####

很显然，判断n是不是质数，最简单的只要暴力从2到n过一遍就可以了

分析：最坏情况（是质数）每个都遍历一遍，时间复杂度O(n)，平均情况由于质数分布也是O(n)

##### 2. 开方优化 #####

容易推出，若一个数n不是质数，则它必然有一个因数F≤n。因此，只需要判断 \[2-n\]之间的数即可。

分析：时间复杂度降为O(n)

##### 3. 6n优化 #####

再想一想就会发现，我们对于2、3的倍数做了太多次重复运算：一个数模2不等于0，那么它模4、6、8也都不会等于0；3也一样。这些重复在6次的周期内会重复4次。因此，我们可以考虑优化它们，即：  
除特殊情况外，只需考虑因数为6n−1和6n+1的情况（n为正整数）

<table> 
 <tbody> 
  <tr> 
   <td></td> 
   <td><code>template&lt;class IntT&gt; bool isPrime(IntT n) { </code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>if (n &lt;= 1)</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>return false;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>if (n &lt;= 5 &amp;&amp; n != 4)</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>return true;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>if (n % 2 == 0 || n % 3 == 0)</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>return false;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>for (IntT i=5; i*i&lt;=n; i+=6) { </code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>if (n % i == 0 || n % (i + 2) == 0)</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>return false;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>}</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>return true;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>}</code></td> 
  </tr> 
 </tbody> 
</table>

分析：虽然时间复杂度没降，但速度显著提升了

#### 筛法 ####

这里就不详细讲解了，主要是运用已知的质数遍历，减少求范围内质数时重复的遍历次数（筛法都会更耗空间）。

##### 1. 埃氏筛法 #####

（注：这里加了个小小的优化，在第二层循环里，j初始化为`i*i`）

<table> 
 <tbody> 
  <tr> 
   <td></td> 
   <td><code>template&lt;class IntT&gt; IntT get_primes_num(IntT n) { </code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>if (n &lt;= 1)</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>return 0;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>bool *isPrimes = new bool[n + 1];</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>IntT *primes = new IntT[n - 1],</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>pn = 0;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>memset(isPrimes, 1, n - 1);</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>for (IntT i=2; i&lt;=n; i++) { </code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>if (isPrimes[i]) { </code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>primes[pn++] = i;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>for (IntT j=i*i; j&lt;=n; j+=i)</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>isPrimes[j] = false;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>}</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>}</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>delete isPrimes;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>delete primes;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>return pn;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>}</code></td> 
  </tr> 
 </tbody> 
</table>

时间复杂度为O(nln⁡ln⁡n)（这一堆原理自己搜去，我自己也讲不清楚）

##### 2. 欧拉筛法 #####

对于埃氏筛法的进一步优化

<table> 
 <tbody> 
  <tr> 
   <td></td> 
   <td><code>template&lt;class IntT&gt; IntT get_primes_num(IntT n) { </code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>if (n &lt;= 1)</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>return 0;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>bool *isPrimes = new bool[n + 1];</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>IntT *primes = new IntT[n - 1],</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>pn = 0;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>memset(isPrimes, 1, n - 1);</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>for (IntT i=2; i&lt;=n; i++) { </code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>if (isPrimes[i])</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>primes[pn++] = i;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>for (IntT j=0; i*primes[j]&lt;=n; j++) { </code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>isPrimes[i * primes[j]] = false;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>if (i % primes[j] == 0)</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>break;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>}</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>}</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>delete isPrimes;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>delete primes;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>return pn;</code></td> 
  </tr> 
  <tr> 
   <td></td> 
   <td><code>}</code></td> 
  </tr> 
 </tbody> 
</table>

时间复杂度为O(n)。注意：在n不大的时候，欧拉筛法与埃氏筛法比并不具有绝对优势，还有可能被反超（毕竟只是优化了个ln⁡ln⁡n），几乎相当于拼常数

### 测试 ###

好了，接下来就是我们的核心——测试环节了。我这里在本机使用了一个基于`std::chrono`的封装计时库（程序主体部分运行至少6s）。记录以微秒（μs，百万分之一秒）为单位。  
（windows x64 AMDRyzen5-5600H）

回顾一下两种情况：

1.  寻找 2-100,000 内的质数个数
2.  寻找 10,000,001-10,009,999 内的质数个数（筛法：你故意找茬是吧）

### 总结 ###

平时做算法题的时候，如果说是**从1或者一个较小的数开始计数的**，那么建议使用**埃氏筛**（欧拉筛实现起来更烦，还不一定拼得过加了优化的埃式筛法（ps：优化加了容易数据容易溢出，建议用`unsigned long long`），要么去掉优化老老实实用`j=2i`）；  
反之，如果是都在一个较高位的，那么建议使用**6n优化**，容易写，比平方优化效率也高很多。这时候再使用两次筛法的差值，时间就容易爆掉（就算一次也容易爆时间）。

好了，以上就是本人对C++质数判断算法的时间测试的所有内容了，初次创作，如有错误欢迎指出ヾ(^▽^\*)))