求素数优化算法

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

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

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), 速度极大的提高了。

后言

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

总结

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

说点什么

avatar
  Subscribe  
提醒