C++中如何判断素数 |21xrx.com

C++中如何判断素数

2023-06-27 19:48:15 深夜i -- --

C++ 素数判断

素数是指只能被1和它本身整除的正整数，对于C++程序员来说，判断一个数是否为素数是一项基本任务。本文将介绍几种判断素数的方法。

方法一：试除法

试除法是指从2开始，不断尝试将该数除以2到sqrt(n)之间的数，如果能整除，说明该数不是素数，否则就是素数。具体实现代码如下：

 c++
bool isPrime(int n) {
  if(n < 2) return false;
  int m = sqrt(n);
  for(int i = 2; i <= m; i++) {
    if(n % i == 0) return false;
  }
  return true;
}

方法二：埃氏筛法

埃氏筛法是一种可以用来快速获得小于某个数的所有素数的算法，它的基本思想是将每个数标记成“已经筛选过了”或“还没有被筛选”。具体实现代码如下：


bool isPrime(int n) {
  if(n < 2) return false;
  bool arr[n+1];
  memset(arr, true, sizeof(arr));
  for(int i = 2; i <= sqrt(n); i++) {
    if(arr[i]) {
      for(int j = i*i; j <= n; j += i) {
        arr[j] = false;
      }
    }
  }
  return arr[n];
}

方法三：米勒-拉宾素性检验

米勒-拉宾素性检验是一种概率性算法，其基本思想是对于一个奇数n，随机选择一个整数a，判断a是否为n的因数，如果是，则n为合数，如果不是，则需要进行更多的判定，直到一定的概率判定为素数。具体实现代码如下：


ll quickPow(ll x, ll p, ll mod) {
  ll ans = 1 % mod;
  while(p > 0) {
    if(p & 1) ans = ans * x % mod;
    x = x * x % mod;
    p >>= 1;
  }
  return ans;
}
bool MillerRabin(ll n) {
  if(n == 2) return true;
  if(n < 2 || n % 2 == 0) return false;
  ll d = n-1;
  for(; d % 2 == 0; d /= 2) {
    ll a = rand() % (n-2) + 2;
    ll x = quickPow(a, d, n);
    ll y = 0;
    for(; d != n-1 && x != 1 && x != n-1; d *= 2) {
      y = x;
      x = x * x % n;
    }
    if(x != n-1 && y % 2 == 0) return false;
  }
  return true;
}

以上三种方法都可以有效地判断一个数是否为素数，程序员可以根据自己的实际需求选择合适的方法。

上一篇: idea打包java可执行jar包

下一篇: C++双重释放问题

评论区

()

相似文章