C++中判断质数的方法 |21xrx.com

C++中判断质数的方法

2023-07-02 13:49:02 深夜i 8 0

C++ 判断质数方法

C++是一种高效、快速的编程语言，可以用来解决各种问题，包括判断质数。在数学中，质数是除了1和自身以外没有其他因数的正整数。C++提供了多种方法来判断一个数字是否是质数。

一般方法：

最直接的方法就是用一个循环来检查一个数字是否有除1和本身以外的因子。这种方法的缺点是效率相对较低。代码如下：

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

用sqrt方法：

由于一个数字的因子总是成对出现，因此如果从2开始检查，一直到n的开方，就可以大大提高效率。代码如下：

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

用质数表方法：

如果多次需要判断某个数字是否是质数，最好的方法是先生成一个质数表，然后直接查表即可。代码如下：

int prime[SIZE],num=0;
bool isPrime[SIZE]=false;
for(int i=2;i<SIZE;i++){
  if(!isPrime[i]){
    prime[num++]=i;
    for(int j=i*i;j<SIZE;j+=i){
      isPrime[j]=true;
    }
  }
}

这个方法先标记2~SIZE范围内的所有质数，然后将它们存储在一个数组中以备需要时使用。对于任何一个数字，只需查看质数表中是否有它即可。

判断质数在计算机中是一个常见的问题，C++提供了多种解决方案。根据实际需要选择适合自己的方法，不仅可以提高效率，还可以将程序变得更加简洁易读。

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

下一篇: C++如何实现将屏幕数据直接输出到文件？

评论区

相似文章