C++判断质数的实现方法

一、是否为质数的定义

质数是指只能被1和自身整除的正整数。判断一个数是否为质数，即判断它能否被除1和自身以外的正整数整除。

二、暴力法判断质数

暴力法是一种最原始的判断质数的方法，即对于一个数n，依次判断2~n-1是否能够整除n。如果能整除，则认为n不是质数；如果不能整除，则认为n是质数。

bool isPrime(int n) {
    if(n 

这种方法的时间复杂度为O(n)，运行时间随着n的增大而增大，不适用于大数的判断。需要使用更高效的算法。

三、优化判断质数的方法

1. 去掉偶数判断

所有大于2的偶数都不是质数，因为它们都可以被2整除。所以，在判断一个数是否为质数时，可以先判断它是否是2，如果是2，则是质数；如果不是2，则去掉偶数进行判断。

bool isPrime(int n) {
    if(n