C++实现素数查找与求和 |21xrx.com

C++实现素数查找与求和

2023-07-04 20:24:05 深夜i -- --

C++ 素数查找求和

素数指的是只能被1和本身整除的数字，如2、3、5、7等等。在计算机程序中，查找和对素数进行求和是一个常见的问题。C++编程语言提供了各种方法来解决这个问题。

要查找素数，最简单的方法是用一个循环从2到N-1（N为待查找的数），检查N是否可以被每个数整除。但是，这种算法的效率很低，当N很大时耗费的时间很长。更好的方法是用“埃氏筛法”和“欧拉筛法”。

埃氏筛法是一种简单但有效的算法，它可以通过预处理一些信息来快速检测给定范围内的所有素数。该方法的基本思想是将所有数标记为“未被筛选”，然后从2开始，将所有2的倍数标记为“已被筛选”，之后再从3开始，将所有3的倍数标记为“已被筛选”，依此类推，最终未被标记的数即为素数。下面是埃氏筛法的C++代码：


#include <iostream>
#include <cstring>
using namespace std;
void eratosthenes(int n)
{
  bool prime[n];
  memset(prime, true, sizeof(prime));
  for (int p=2; p*p<=n; p++)
  {
    if (prime[p])
    {
      for (int i=p*p; i<=n; i+=p)
        prime[i] = false;
    }
  }
  for (int p=2; p<=n; p++)
    if (prime[p])
     cout << p << " ";
}
int main()
{
  int n = 50;
  cout << "Prime numbers between 2 and " << n << " are: ";
  eratosthenes(n);
  cout << endl;
  return 0;
}

欧拉筛法是一种更高效的算法，它通过预处理一些数据来逐步筛选出素数。该方法的基本思想是在埃氏筛法的基础上，除掉所有倍数，不再重复筛查。具体实现时，对每个合数只除以其最小质因子一次，这样每个合数只会被其最小质因子筛掉一次，从而避免了重复筛查。下面是欧拉筛法的C++代码：


#include <iostream>
#include <cstring>
using namespace std;
void euler(int n)
{
  bool prime[n+1];
  memset(prime, true, sizeof(prime));
  for (int p=2; p<=n; p++)
  {
    if (prime[p])
      cout << p << " ";
    for (int i=2; i<=n/p; i++)
      prime[i*p] = false;
  }
}
int main()
{
  int n = 50;
  cout << "Prime numbers between 2 and " << n << " are: ";
  euler(n);
  cout << endl;
  return 0;
}

除了查找素数，对素数进行求和也是一个常见的问题。我们可以通过遍历素数并将它们相加来解决这个问题。下面是一个简单的C++程序：


#include <iostream>
using namespace std;
int main()
{
  int n, sum = 0;
  cout << "Enter the upper limit: ";
  cin >> n;
  for (int i=2; i<=n; i++)
  {
    bool isPrime = true;
    for (int j=2; j*j<=i; j++)
    {
      if (i % j == 0)
      
        isPrime = false;
        break;
      
    }
    if (isPrime)
      sum += i;
  }
  cout << "The sum of all prime numbers between 2 and " << n << " is " << sum << endl;
  return 0;
}

C++提供了许多方法来解决素数查找和求和问题。选择最适合您需求的算法和数据结构可以大幅提高程序效率。

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

下一篇: DevC++如何更改背景色？

评论区

()

相似文章