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

C++语言中如何判断素数

2023-06-28 21:29:28 深夜i -- --

C++ 判断素数

素数是指只能被1和本身整除的正整数。素数是数学中非常重要的概念，而在C++语言中，判断一个数是否是素数也是常见的程序题目。本文将介绍C++语言中如何判断素数。

一般来说，判断素数的方法有两种：试除法和筛法。试除法就是对于每个数字进行一次除法运算，判断能否整除，这种方法比较直接，但是对于大数运算效率较低。筛法则是先列举出所有素数，然后依据素数的倍数判断其他数字是否是素数，这种方法可以大量减少判断次数，对于大数运算效率较高。下面我们将介绍两种方法。

1. 试除法

首先，判断一个数是否为素数就是从2开始到这个数的平方根之间，依次判断是否有因子。如果存在因子则不是素数，否则就是素数。代码实现如下：


bool isPrime(int num) {
  if (num <= 1)  // 1不是素数
    return false;
  
  for (int i = 2; i <= sqrt(num); i++) {
    if (num % i == 0)  // 如果存在因子
  }
  return true; // 否则是素数
}

上述代码中，我们首先判断num是否小于等于1，因为1不是素数。然后从2开始到num的平方根之间，循环判断是否存在因子，如果存在则说明num不是素数。如果循环结束后都没有找到因子，则说明num是素数。

2. 筛法

筛法的核心思想是：先预处理出一定范围内的素数，然后通过这些素数来筛选出其他数是否是素数。常见的筛法有埃氏筛和线性筛。

埃氏筛的具体思路是，从2开始依次枚举数字，对于每个数，枚举其倍数，并标记为非素数。当枚举到n时，所有没有被标记的数字都是素数。


void primeSieve(int n) {
  vector<bool> isPrime(n + 1, true);
  for (int i = 2; i <= n; i++) {
    if (isPrime[i]) { // 如果i是素数
      cout << i << " ";
      for (int j = i * i; j <= n; j += i) { // 标记i的倍数为非素数
        isPrime[j] = false;
      }
    }
  }
}

在上述代码中，我们首先定义了一个长度为n+1的bool数组，来标记每个数字是否是素数。然后从2开始依次枚举数字，对于每个数字，如果它是素数就输出，并标记其倍数为非素数。

线性筛的具体思路是，在埃氏筛的基础上，对于每个合数，只用最小质因子去更新它。因此，不同于埃氏筛的把一个数的所有素数因子全部枚举，线性筛每个合数只被它的最小质因子筛掉，保证每个合数只会被筛一次。代码实现如下：


void primeSieve(int n) {
  vector<int> primes; // 存储素数
  vector<int> isPrime(n + 1, 0); // 用来标记数字是否是素数，0表示未标记，1表示是素数
  for (int i = 2; i <= n; i++) {
    if (isPrime[i] == 0) { // 如果i是素数
      primes.push_back(i); // 加入素数列表
      isPrime[i] = i; // 标记i的最小质因子为i
    }
    for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {
      isPrime[i * primes[j]] = primes[j]; // 标记i*primes[j]的最小质因子为primes[j]
      if (i % primes[j] == 0) { // 如果i被primes[j]整除，则不用再更新了
        break;
      }
    }
  }
}

上述代码中，我们首先定义了一个向量primes来存储素数，一个向量isPrime来标记每个数字是否是素数。isPrime中初始值都为0，表示未标记。然后从2开始依次枚举数字，如果该数字未被标记，则将其加入素数列表，并将其最小质因子标记为它本身。接着，依次枚举素数列表中的元素primes[j]，并用i * primes[j]去更新isPrime中对应的元素。如果i被primes[j]整除，则说明i * primes[j]的最小质因子是primes[j]。由于每个合数只被它的最小质因子筛掉，因此每个合数只会被筛一次。

总结

在C++语言中，判断素数有两种方法：试除法和筛法。试除法就是对于每个数字进行一次除法运算，判断能否整除；筛法则是先列举出所有素数，然后依据素数的倍数判断其他数字是否是素数。埃氏筛和线性筛都是常用的筛法。对于小数的判断，可以使用试除法；对于大数的判断，可以使用筛法。

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

下一篇: VC++6.0能否编写游戏？

评论区

()

相似文章