在比赛或者工作时，有时候会经常要求我们编程求素数，但是我们自己写出来的时间复杂度太高，所以我在这里做个总结。

先贴上最终函数，该段代码在开启最大代码优化时，可以直接内嵌进调用程序中，使得速度更加极致。

C语言

// 对 n 进行素数判断
inline static int is_prime(int n)
{
    int i;

    if (n == 2)
    {
        return 1;
    }

    if (n < 2 || n % 2 == 0)
    {
        return 0;
    }

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

    return 1;
}

Python

Python 的话，由于本身是脚本语言，所以很难做到很快，一般都是用C语言进行计算的。

# 对 n 进行素数判断
# 注意：请不要传入浮点数
def is_prime(n):
    if (n == 2):
        return True

    if (n < 2 or n % 2 == 0):
        return False

    i = 3
    while( i * i <= n):
        if( n % i == 0):
            return False
        i += 2

    return True

原理

根据定义

根据概念判断：如果一个正整数只有两个因子, 1 和 p，则称 p 为素数。所以根据定义我们写出如下函数：

int is_prime(int n)
{
    int i;
    if (n < 2)
    {
        return 0;
    }

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

    return 1;
}

时间复杂度为O(n)，可以说是很差的算法。

上面的函数做了很多不必要的动作，比如偶数的判断，因为除了2本身以外，其他的大于0的偶数都有因子2。

偶数优化

这面这段代码，去掉了偶数的判断。

int is_prime(int n)
{
    int i;
    if (n < 2)
    {
        return 0;
    }
    if (n == 2)
    {
        return 1;
    }

    for (i = 3; i < n; i += 2)
    {
        if (n % i == 0)
        {
            return 0;
        }
    }

    return 1;
}

时间复杂度O(n/2), 速度提高一倍，比之前的性能更优化了一点。

根据定理进行优化

定理: 如果 n 不是素数, 则 n 有满足 1<d<=sqrt(n) 的一个因子d。简单点说就是，如果 n 不是素数, 则在 1<d<=sqrt(n) 的范围中，至少有一个 d 可以 n % d == 0 。

int is_prime(int n)
{
    int i;

    if (n == 2)
    {
        return 1;
    }

    if (n < 2 || n % 2 == 0)
    {
        return 0;
    }

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

    return 1;
}

时间复杂度O(sqrt(n)/2), 速度极大的提高了。

后言

其实还可以将已经计算出来的素数数组带到算法中去的，这样的算法速度会更快，但是其由于其不符合高内聚、低耦合的编程思想，这里就不提了。这样的算法可以用于特定程序来做优化，但是不适合普遍程序。

总结

算法的优化是数量级别的。