C++程序实现素数的查找 |holyya.com

C++程序实现素数的查找

2023-07-04 21:39:26 深夜i -- --

C++ 程序素数查找实现

C++程序是一门高效、快速的编程语言，可以用来实现各种各样的算法和数据结构。其中，素数的查找是非常重要的一项任务，因为素数在密码学、计算机科学以及其他许多领域中都有着广泛的应用。

要实现素数的查找，我们首先需要明确素数的定义：素数指只能被1和本身整除的自然数，即只有两个约数的数。根据这个定义，我们可以写出一个简单的C++程序，用来检查一个数是否为素数。


#include <iostream>
using namespace std;
bool is_prime(int n) {
 if (n <= 1) return false;
 for (int i = 2; i * i <= n; i++) {
  if (n % i == 0) return false;
 }
 return true;
}
int main() {
 int n;
 cout << "Enter a number: ";
 cin >> n;
 if (is_prime(n))
  cout << n << " is a prime number." << endl;
  else
  cout << n << " is not a prime number." << endl;
 
 return 0;
}

这个程序接受用户输入一个整数，然后调用is_prime函数来判断这个数是否为素数。is_prime函数通过遍历2到sqrt(n)的所有整数，来判断n是否能被其中任何一个整数整除。如果能够被整除，则n不是素数，否则n是素数。

这个程序可以很方便地扩展到查找一定范围内的所有素数。我们可以使用一个数组来保存素数，然后在每次判断时遍历数组，并用is_prime函数来判断当前的整数是否为素数。这种方法虽然相对比较慢，但是可以有效地找到一定范围内的所有素数。


#include <iostream>
#include <vector>
using namespace std;
bool is_prime(int n) {
 if (n <= 1) return false;
 for (int i = 2; i * i <= n; i++) {
  if (n % i == 0) return false;
 }
 return true;
}
int main() {
 int n;
 cout << "Enter the range: ";
 cin >> n;
 vector<int> primes;
 for (int i = 2; i <= n; i++) {
  bool flag = true;
  for (int j = 0; j < primes.size(); j++) {
   if (i % primes[j] == 0)
    flag = false;
    break;
   
  }
  if (flag && is_prime(i)) {
   primes.push_back(i);
  }
 }
 for (int i = 0; i < primes.size(); i++) {
  cout << primes[i] << endl;
 }
 return 0;
}

这个程序同样接受用户输入一个整数n，然后找到2到n之间的所有素数，并将它们保存在一个vector 中。在每次遍历时，程序使用一个flag来判断当前整数是否可以被vector中的已有素数整除，如果不行，则调用is_prime函数来判断当前整数是否为素数，并将素数加入到vector中。最后程序遍历vector，输出所有素数。

这样，我们就可以通过C++程序来实现素数的查找了。无论是针对单个数的判断，还是针对一定范围内的素数查找，C++都可以提供快速高效的算法和实现。通过不断学习和实践，我们可以更好地掌握这个强大的编程语言，为各种计算机科学和工程领域的开发和研究提供更好的支持。

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

下一篇: Dev C++运行程序无输出，如何解决？

评论区

()

相似文章