关于质数

质数 (prime number) 又称素数，有无限个。

一个大于 1 的自然数，除了 1 和它本身外，不能被其他自然数整除，换句话说就是该数除了 1 和它本身以外不再有其他的因数; 否则称为合数。

根据算术基本定理，每一个比 1 大的整数，要么本身是一个质数，要么可以写成一系列质数的乘积; 而且如果不考虑这些质数在乘积中的顺序，那么写出来的形式是唯一的。

最小的质数是 2。

方法一

从2开始寻找，直到 n - 1 。如果没有找到可以整除这个数的数，那么这个数是素数。

#include <iostream>

bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }

    for (int i = 2; i < n; ++i) {
        if (n % i == 0) {
            return false; // 如果 n 能被 i 整除，那么 n 不是素数
        }
    }

    return true; // 如果在 2 到 n-1 的范围内都找不到能整除 n 的数，则 n 是素数
}

方法二

从2开始，直到n开方+1，如果没有找到可以整除这个数的数，那么这个数是素数。

#include <iostream>
#include <cmath>

bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }

    // 仅试除到sqrt(n)
    int sqrt_n = sqrt(n);
    for (int i = 2; i <= sqrt_n; ++i) {
        if (n % i == 0) {
            return false; // 如果 n 能被 i 整除，那么 n 不是素数
        }
    }

    return true; // 如果在 2 到 sqrt(n) 的范围内都找不到能整除 n 的数，则 n 是素数
}

方法三

素数除了2，首先不能是偶数。再判断其是否能被某一奇数整除。

#include <iostream>
#include <cmath>

bool isPrime(int n) {
    if (n <= 1) {
        return false;
    }

    // 排除2以外的偶数
    if (n % 2 == 0) {
        return (n == 2); // 如果是2则是素数，否则不是素数
    }

    // 仅试除到sqrt(n)
    int sqrt_n = sqrt(n);
    for (int i = 3; i <= sqrt_n; i += 2) {
        if (n % i == 0) {
            return false; // 如果 n 能被 i 整除，那么 n 不是素数
        }
    }

    return true; // 如果在 3 到 sqrt(n) 的范围内都找不到能整除 n 的奇数，则 n 是素数
}

方法四

6k±1优化，利用了素数除了2和3以外都可以表示为6k±1的形式这一特性。通过仅仅检查6k±1的数，可以有效地减少试除的次数，提高素数判断的效率。

// 检查一个数是否为素数
bool isPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0) return false;
    }
    return true;
}

算法思想：

• 排除一些特殊情况：首先检查输入的数是否小于等于1或者等于2或3，如果是的话，直接返回相应的结果，因为1不是素数，2和3是素数。
• 排除大量的非素数：在循环中，以6为步长逐个检查可能是素数的数，即6k-1和6k+1（除了2和3以外的素数都可以表示为6k-1或6k+1的形式），如果这两个数中有一个能整除n，则n不是素数。
• 仅检查到sqrt(n)：循环条件为i * i <= n，这样可以避免重复检查过大的数，因为如果存在一个大于sqrt(n)的因子，那么一定存在一个小于sqrt(n)的因子。
• 通过前面排除的情况，剩下的数就是可能是素数的数，依次进行试除，如果找到能整除n的数，则n不是素数，否则n是素数。