求素数的C语言代码优化

最新推荐文章于 2025-03-29 13:32:02 发布

Cyrus_wen

最新推荐文章于 2025-03-29 13:32:02 发布

阅读量6.3k

点赞数 10

分类专栏：程序员之路

本文链接：https://blog.csdn.net/Cyrus_wen/article/details/78467111

版权

程序员之路专栏收录该内容

3 篇文章

订阅专栏

为了方便叙述，这里我们举一个例子。求100到200之间的素数。
方法一：判断一个数是否为素数我们首先想到的方法就是用这个数除以1到该数之间的每一个整数，如果都不能整除，那么该数为素数。例如求101是否为素数就让101除以2到100之间的数，都不能整除，所以101为素数。
可得代码：

#include<stdio.h>
int main()
{
    int i=0;
    int j=0;
    for(i=100;i<=200;i++)
    {
        for(j=2;j<i;j++)
        {
            if(i%j==0)
                break;
        }
    if(i==j)
    printf("%d\t",i);
    }
    return 0;
}

得到结果：
这里写图片描述
这里得到的结果正确，但是我们发现这样写的程序计算数字较小的情况可以很快，但是如果我们要判断大数量级的数呢？因此，我们要缩短时间复杂度。
这里得到方法二：我们假设一个数为x,如果该数不是一个素数，那么x一定可以由表达式x=a*b表示，所以当a为2时b可得最大值x/2;当b=2时，a为最大值x/2。因此，我们只需要用x除以2到x/2之间的数即可，如果都不能整除，则说明x为素数。

#include<stdio.h>
int main()
{
    int i=0;
    int j=0;
    for(i=100;i<=200;i++)
    {
        for(j=2;j<i/2;j++)
        {
            if(i%j==0)
                break;
        }
    if(j==i/2)
    printf("%d\t",i);
    }
    return 0;
}

结果与方法一相同：
这里写图片描述
写到这里，我们觉得代码时间复杂度已经减小，但是由方法二得到启发，我们发现a和b一定相等或者一大一小，那么我们只需要除以较小的数即可，那么较小的数的范围是多少呢？当a=b时，a=sqrt(x),所以我们只需除以2到sqrt(x)，判断能否被整除。另外，x如果为偶数，那么x一定不是素数。所以代码，再次被优化。
我们得到方法三：

#include<stdio.h>
#include<math.h>
int main()
{
    int i=100;
    for(i=101;i<=200;i+=2)
    {
        int j=2;
        for(j=2;j<sqrt((double)i);j++)
        {
            if(i%j==0)
            {
                break;                  
            }
        }
            if(j>=sqrt((double)i))
            {
                printf("%d\t",i);
            }

    }
    return 0;
}