经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » 编程经验 » 查看文章
素数判定算法 初级
来源:cnblogs  作者:qiyuewuyi2333  时间:2024/5/29 9:10:14  对本文有异议

前置知识

Cpp实现

基础算法

  1. // base method
  2. bool basement(int num)
  3. {
  4. for (int i = 2; i <= sqrt(num); ++i)
  5. {
  6. if (num % i == 0)
  7. return false;
  8. }
  9. return true;
  10. }

证明

筛法初步

根据初等数学的知识,如果一个数不是2的倍数,那么它肯定不是2的倍数的倍数,所以,进一步的我们可以对上面的基础算法进行优化

  1. // sieve first step
  2. bool sieve2Method(int num)
  3. {
  4. if (num == 2)
  5. return true;
  6. if (num % 2 == 0 || num < 2)
  7. return false;
  8. else
  9. {
  10. for (int i = 3; i * i <= num; i += 2)
  11. {
  12. if (num % i == 0)
  13. {
  14. return false;
  15. }
  16. }
  17. return true;
  18. }
  19. }

轮转筛法

6k ± 1 形式轮换筛法(轮转筛法)(Wheel Factorization)。

轮转筛法的基本原理是利用模数(在这里是6)的性质来减少需要检查的数。具体到6k ± 1形式,这个形式背后的理由如下:

  • 整数 n 可以表示为 6??+??,其中 ?? 是0到5之间的一个整数。
  • 对于 ??=0,2,3,4,这些数都可以被2或3整除(即它们是合数)。
  • 只有 ??=1 和 ??=5(即 6??+1 和 6???1)可能是质数。
  1. bool isPrime_3(int num)
  2. {
  3. if (num == 2 || num == 3)
  4. return 1;
  5. // 不在6的倍数两侧的一定不是质数
  6. if (num % 6 != 1 && num % 6 != 5)
  7. return 0;
  8. int tmp = sqrt(num);
  9. // 在6的倍数两侧的也可能不是质数
  10. for (int i = 5; i <= tmp; i += 6)
  11. if (num % i == 0 || num % (i + 2) == 0)
  12. return 0;
  13. // 排除所有,剩余的是质数
  14. return 1;
  15. }

埃拉托斯特尼筛法生成素数表

根据上面我们的初步想法,我们可以进一步的将用于筛选的因子扩大。
但是,这种筛法的核心思想之一是:
如何确定筛选因子
既然我们要做到高效,那么这些筛选因子之间的筛取最好没有重合,或者重合度很小,至少它不应该完全重复筛取,对吧?
考虑2,3,4这三个数。
经过简单运算,我们知道将3作为筛选因子,是可以筛取到2晒不出的数字的,比如说9,但是4,因为它有因子2,所以它所有筛取的数字,均早就被2筛取过了。
所以,我们应该选取素数作为筛取因子。

  1. std::vector<bool> sieveOfEratosthenes(int n)
  2. {
  3. std::vector<bool> isPrime(n + 1, true);
  4. isPrime[0] = isPrime[1] = false; // 0和1不是素数
  5. for (int p = 2; p <= std::sqrt(n); ++p)
  6. {
  7. if (isPrime[p])
  8. {
  9. for (int i = p * p; i <= n; i += p)
  10. {
  11. isPrime[i] = false;
  12. }
  13. }
  14. }
  15. return isPrime;
  16. }

但是这里面还有一些实现细节,需要注意:

  • 初始化0 1 索引为false,
  • p <= sqrt(n)
  • i = p * p

我们一个个来说,1 略
2 为什么p<=sqrt(n),这样可以筛全吗?
是可以的,首先我们初始化值为false,这意味着我们只需要筛选出 1 ~ n中的合数即可。
又根据我们上面对于基本方法的循环范围的证明,所以,只要一个数是合数,那么它肯定会在2~ $\sqrt{ n }$ 之间
所以,我们可以通过反向推导,如果某一个因子,能够通过倍加自己,或者可以理解为以自己为步长进行步进,那么他肯定能够到达那些以它为因子的合数位置上

3 为什么 内层的i要初始化为 $p * p$ ,而不是 $p * 2$之类的
这是因为要防止和之前已经筛过的部分发生重合,比如3个2和2个3

欧拉筛法

从上面埃氏筛法,我们确立了可以通过筛取合数,从而反向获取素数的思路。但显然,它仍有优化的空间,那就是重复的筛取。而欧拉筛法正为此而生。

欧拉筛,又称线性筛,时间复杂度只有O(n)

在埃氏筛法的基础上,让每一个合数都只被它的最小质因子筛选一次,以达到不重复筛选的目的,大大地节省了时间,从埃氏筛的O(n2)降到O(n)级别

我们想要阻止重复标记的发生,就需要一种规则,也就是说只让标记以某一种特定的形式or规律被标记,在欧拉筛法中,这表现为,只用最小素因子去标记

为了知道最小素因子,我们很自然地需要一个表维护已知的素数

欧拉筛法正确性的证明

实现

  1. vector<int> eulerSieve(int n)
  2. {
  3. std::vector<bool> isPrime(n + 1, true);
  4. std::vector<int> primes; // 素数集合
  5. isPrime[0] = isPrime[1] = false; // 0和1不是素数
  6. for (int i = 2; i <= n; ++i)
  7. {
  8. if (isPrime[i])
  9. {
  10. primes.push_back(i);
  11. }
  12. for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j)
  13. {
  14. isPrime[i * primes[j]] = false;
  15. if (i % primes[j] == 0)
  16. break;
  17. }
  18. }
  19. return primes;
  20. }

Miller-Rabin算法。
暂时不看~

Miller-Rabin算法

Miller-Rabin算法是一种概率性质数测试算法,可以用来判断一个大整数是否为质数。该算法基于数论中的一些深刻性质,其优点在于对大数的判断效率非常高。虽然它是一个概率算法,但通过多次测试,可以将错误率降到非常低。

Miller-Rabin算法步骤

Miller-Rabin算法基于Fermat小定理以及以下两个重要的数学性质:

  1. 如果 ?? 是一个质数,则对于任何整数 ?? 满足 $1≤??≤???1$,有 $??^{n-1} ≡ 1 mod????$。
  2. 如果 ?? 是一个奇质数,则存在一个唯一的表达式 $???1=2^{s}???$,其中 ?? 是一个奇数,$??≥1$。

具体步骤

  1. 将 ???1 表示为 $2^{s}???$:

    • 例如,对于 ??=15n=15,我们有 ???1=14n?1=14,即 14=2?714=2?7,这里 ??=7d=7 和 ??=1s=1。
  2. 随机选择一个整数 ?? 其中$1 \le a \le n-1$

    • 如果存在 $????≡1mod????$,则 ??n 可能是一个质数。
    • 对于 ??=0,1,…,???1,如果存在 $??{2?????}≡?1mod????$,则 ?? 可能是一个质数。
  3. 重复上述测试 k 次:

    • 选择不同的 ?? 进行多次测试。
    • 如果所有测试均通过,则 ?? 很可能是一个质数。
    • 如果有一次测试失败,则 ?? 不是质数。

Miller-Rabin算法的伪代码

  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <ctime>
  4. // 使用快速幂算法计算 (base^exponent) % mod
  5. long long mod_exp(long long base, long long exponent, long long mod) {
  6. long long result = 1;
  7. base = base % mod;
  8. while (exponent > 0) {
  9. if (exponent % 2 == 1) {
  10. result = (result * base) % mod;
  11. }
  12. exponent = exponent >> 1;
  13. base = (base * base) % mod;
  14. }
  15. return result;
  16. }
  17. // Miller-Rabin测试的核心函数
  18. bool miller_test(long long d, long long n) {
  19. long long a = 2 + rand() % (n - 4); // 随机选择 2 <= a <= n-2
  20. long long x = mod_exp(a, d, n);
  21. if (x == 1 || x == n - 1) {
  22. return true;
  23. }
  24. while (d != n - 1) {
  25. x = (x * x) % n;
  26. d *= 2;
  27. if (x == 1) {
  28. return false;
  29. }
  30. if (x == n - 1) {
  31. return true;
  32. }
  33. }
  34. return false;
  35. }
  36. // Miller-Rabin 素性测试
  37. bool is_prime(long long n, int k) {
  38. if (n <= 1 || n == 4) {
  39. return false;
  40. }
  41. if (n <= 3) {
  42. return true;
  43. }
  44. // 将 n-1 表示为 2^s * d
  45. long long d = n - 1;
  46. while (d % 2 == 0) {
  47. d /= 2;
  48. }
  49. // 进行 k 次测试
  50. for (int i = 0; i < k; i++) {
  51. if (!miller_test(d, n)) {
  52. return false;
  53. }
  54. }
  55. return true;
  56. }
  57. int main() {
  58. srand(time(0)); // 初始化随机数生成器
  59. long long n;
  60. int k = 5; // 测试次数
  61. std::cout << "Enter a number to check if it is prime: ";
  62. std::cin >> n;
  63. if (is_prime(n, k)) {
  64. std::cout << n << " is a prime number." << std::endl;
  65. } else {
  66. std::cout << n << " is not a prime number." << std::endl;
  67. }
  68. return 0;
  69. }

代码解析

  1. 快速幂算法mod_exp函数用于计算 (????????????????????????)mod????????(baseexponent)modmod,以高效地进行大数幂运算。
  2. Miller-Rabin测试的核心函数miller_test函数进行一次Miller-Rabin测试,通过随机选择基数 ?? 并进行多次平方检验来判断 ?? 是否可能是质数。
  3. 素性测试函数is_prime函数调用 miller_test 函数进行多次测试,以概率性的方式判断 ??n 是否为质数。

Miller-Rabin算法的优点

  • 高效:对于大数,Miller-Rabin测试比许多其他算法更高效。
  • 可调性:通过增加测试次数 ??,可以降低误判率,使得算法在实际应用中非常可靠。

原文链接:https://www.cnblogs.com/qiyuewuyi/p/18218594

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号