C++实现素数的查找和排序 |21xrx.com

C++实现素数的查找和排序

2023-07-11 22:16:06 深夜i 13 0

C++ 素数查找排序

在算法中，素数一直是一个重要的概念。由于素数在数学上的特殊性质，它们被广泛应用于密码学、暴力破解、压缩等领域。而在C++编程中，实现素数的查找和排序同样也是一个重要的话题。

实现素数的查找，最简单的方法就是暴力枚举法。对于每一个数，我们都判断它是否是素数。如果是，就将它存储到一个容器中，否则就继续枚举。代码如下：

#include <iostream>
#include <vector>
using namespace std;
bool isPrime(int n) {  // 判断素数
  if (n < 2) return false; // 小于2的数不是素数
  for (int i = 2; i <= sqrt(n); i++) {
    if (n % i == 0) 则不是素数
    
  }
  return true;
}
vector<int> findPrime(int n) {  // 查找前n个素数
  vector<int> res;
  int cnt = 0, i = 2;
  while (cnt < n) {
    if (isPrime(i)) {
      res.push_back(i);
      cnt++;
    }
    i++;
  }
  return res;
}
int main() {
  int n = 10; // 要查找前10个素数
  vector<int> v = findPrime(n);
  for (int i = 0; i < v.size(); i++) {
    cout << v[i] << " ";
  }
  cout << endl;
  return 0;
}

同样的，对于实现素数的排序，也可以使用基本的排序算法。不过由于素数的特殊性质，我们可以采用更高效的排序算法。其中，著名的就是桶排序算法。

桶排序将一组数据分解到多个相对应的桶中，每个桶保存需要排序的数据。然后通过映射函数将待排序数组中的数据放到相应的桶中，再通过桶内排序或者其他排序算法，最后得到排序好的数据。下面是实现素数排序的代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool isPrime(int n) {  // 判断素数
  if (n < 2) return false; // 小于2的数不是素数
  for (int i = 2; i <= sqrt(n); i++) {
    if (n % i == 0)
      return false;  // 如果能被整除
  }
  return true;
}
vector<int> sortPrime(vector<int>& nums) {  // 素数排序
  vector<int> res(nums.size(), 0);
  vector<int> bucket;
  for (int i = 0; i < nums.size(); i++) { // 将素数放入桶中
    if (isPrime(nums[i])) {
      bucket.push_back(nums[i]);
    }
  }
  sort(bucket.begin(), bucket.end());  // 对桶中的素数排序
  int k = 0;
  for (int i = 0; i < nums.size(); i++) {   // 将排序后的结果放入结果数组中
    if (isPrime(nums[i])) {
      res[i] = bucket[k];
      k++;
    }
    else {
      res[i] = nums[i];
    }
  }
  return res;
}
int main() {
  vector<int> nums = 5;
  nums = sortPrime(nums);
  for (int i = 0; i < nums.size(); i++) {
    cout << nums[i] << " ";
  }
  cout << endl;
  return 0;
}

总的来说，实现素数的查找和排序并不难。只需要了解素数的基本概念，然后运用常见的算法和数据结构即可。当然，在具体实现过程中，还需考虑算法的时间复杂度、空间复杂度和效率等方面的问题。这些都需要我们在不断实践中积累和总结。

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

下一篇: 如何彻底卸载C++2015-2019？

评论区

相似文章