✅作者简介：人工智能专业本科在读，喜欢计算机与编程，写博客记录自己的学习历程。
🍎个人主页：小嗷犬的博客
🍊个人信条：为天地立心，为生民立命，为往圣继绝学，为万世开太平。
🥭本文内容：C/C++中的素数判定
更多内容请见👇

• C/C++中的基础数据类型
• C与C++的最常用输入输出方式对比
• C语言竟支持这些操作：C语言神奇程序分享

1.什么是素数

素数又称质数。一个大于 1的自然数，除了 1和它自身外，不能被其他自然数整除的数叫做素数；否则称为合数（规定 1既不是素数也不是合数）。

在许多的程序设计题目中，都会涉及到素数的判断，那我们该如何有效判断素数呢？

2.素数的两种判断方法

2.1 暴力法

2.1.1 从 2 到 √n

根据素数的定义，我们可以使用 逐个试除的方式来判断素数，如果能为要判断的数找到一个除了 1和自身以外的因数，那么它就是合数；反之，就是素数。

而这样的因数的范围必然在 2 ~ √n之间，所以我们便可以得到以下代码。

int isPrime(int n)
{
    if(n <= 1)
    {
        return 0;
    }
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            return 0;
        }
    }
    return 1;
}

该函数就可以判断输入的数是否为素数。

这个范围还可以更进一步地缩小。

2.1.2 6n-1与6n+1

数学上有一个定理，除了 2和 3外，只有形如 6n-1和 6n+1的自然数可能是素数，这里的 n是大于等于 1的整数。

如何理解这个定理呢？
所有自然数都可以写成6n,6n+1,6n+2,6n+3,6n+4,6n+5这6种。
那么我们就可以得到下表。

其中 6n+5可以写作 6n-1，所以除了 2和 3的素数必然形如 6n-1或 6n+1。
于是我们可以写出如下代码。

int isPrime(int n)
{
    if(n <= 1) return 0;
    else if(n == 2 || n == 3) return 1;
    else if(n % 6 != 1 && n % 6 != 5) return 0;
    for (int i = 5; i * i <= n; i++)
    {
        if (n % i == 0)
        {
            return 0;
        }
    }
    return 1;
}

优化后的算法具有更高的效率。

2.2 筛法

暴力算法虽然可以判断某个数是否为素数，但是当它面对大量需要判断的数据时，它的效率会显得十分低下，我们也有更好地方法来求一定范围里的素数，它就是我们的 筛法。

筛法，顾名思义，就是将合数从数据中筛除，剩下的自然就都是素数了。

筛法也分为两种，让我们来逐一介绍。

2.2.1 埃氏筛

埃拉托斯特尼 筛法，简称 埃氏筛，是一种由希腊数学家 埃拉托斯特尼所提出的一种简单检定素数的算法。

要得到自然数n以内的全部素数，必须把不大于根号n的所有素数的倍数剔除，剩下的就是素数。

下面的程序就是通过埃氏筛判断 2 ~ MAXSIZE-1是否为素数。

#define MAXSIZE 10000
int isPrime[MAXSIZE] = {0};
int prime[MAXSIZE];
int cnt = 0;

void sieveOfEratosthenes()
{
    for (int i = 2; i < MAXSIZE; i++)
    {
        isPrime[i] = 1;
    }
    for (int i = 2; i * i < MAXSIZE; i++)
    {
        if (isPrime[i])
        {
            prime[++cnt] = i;
            for (int j = i * 2; j < MAXSIZE; j += i)
            {
                isPrime[j] = 0;
            }
        }
    }
}

埃氏筛的时间复杂度是 O(n*loglogn)，效率相较于原来的暴力算法已经有了很大的提高，但它仍然有具有一定的不足。

对于多个素数的公倍数，可能会被多次筛去。

为了解决这个问题，数学家欧拉优化了算法，于是就有了新的筛法。

2.2.2 欧拉筛

欧拉筛法，简称 欧拉筛或是欧式筛，又因为其 O(n)的时间复杂度而被称为 线性筛。

欧拉筛将合数分解为（最小质因数 * 一个合数）的形式，通过最小质因数来判断当前合数是否已经被标记过，与埃氏筛相比，不会对已经被标记过的合数再进行重复标记，故效率更高。

下面的程序就是通过欧拉筛判断 2 ~ MAXSIZE-1是否为素数。

#define MAXSIZE 10000
int isPrime[MAXSIZE];
int prime[MAXSIZE];
int cnt = 0;

void sieveOfEuler()
{
    for (int i = 2; i < MAXSIZE; i++)
    {
        prime[i] = 1;
        isPrime[i] = 1;
    }
    for (int i = 2; i * i < MAXSIZE; i++)
    {
        if (isPrime[i])
        {
            prime[++cnt] = i;
        }
        for (int j = 1; i * prime[j] < MAXSIZE; j++)
        {
            isPrime[i * prime[j]] = 0;
            //若i为prime[j]的倍数，终止循环，避免重复筛除
            if (i % prime[j] == 0)
                break;
        }
    }
}

在求一定范围中的所有素数时，欧拉筛具有无可比拟的优势，在程序设计中也经常被采用。