判断素数的方法和在C++中的实现

判断素数的方法

素数是指大于1的自然数中，除了1和它本身以外不再有其他因数的自然数，也叫质数。判断一个数是否为素数，常用的方法是暴力法，即将该数从2开始依次除到他的平方根，如果都不能整除，则该数是素数。

在C++中的实现

#include 
#include 
using namespace std;

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

int main() {
  int n;
  cin >> n;
  if (isPrime(n)) {
    cout << n << " is a prime number" << endl;
  } else {
    cout << n << " is not a prime number" << endl;
  }
  return 0;
}

上面的代码实现了一个判断素数的函数，函数接受一个参数n，如果n小于等于1，则直接返回false；如果n大于1，则从2开始，逐步除到n的平方根，如果在这个过程中发现有能够整除n的数，则返回false；如果没有发现，则返回true。