质数的和（多种方案）

梦里梦外; 2022-06-16 05:52 154阅读 0赞

求某个范围内质数的和，例如输入100，则求出小于100的质数和。

PS：下面的三种方法会逐步缩小遍历查找的范围

方法1：

#include<stdio.h>
    
    int IsPrime(int n)
    {
       //判断n是否为质数，如果是返回1，否则返回0
        int i;
        for (i = 2; i < n; i++)//这个地方的遍历范围是【2，n】，在方法2中会缩小遍历范围
        {
            if (n % i == 0)
                return 0;
        }
        return 1;
    }
    
    int main()
    {
        int i, nUpLimit, sum = 0;
        printf("输入一个正整数,下面将求出这个范围内的质数和: ");
        scanf_s("%d", &nUpLimit);
        for (i = 2; i <= nUpLimit; i++)
        {
            if (IsPrime(i))
                sum += i;
        }
        printf("sum=%d\n", sum);
        return 0;
    }

方法2：

#include<stdio.h>
    
    int IsPrime(int n)
    {
       //判断n是否为质数，如果是返回1，否则返回0
        int i;
        for (i = 2; i <= n / 2; i++)//这个地方的遍历范围是【2，n / 2】，在方法3中会进一步缩小遍历范围
        {
            if (n % i == 0)
                return 0;
        }
        return 1;
    }
    
    int main()
    {
        int i, nUpLimit, sum = 0;
        printf("输入一个正整数,下面将求出这个范围内的质数和: ");
        scanf_s("%d", &nUpLimit);
        for (i = 2; i <= nUpLimit; i++)
        {
            if (IsPrime(i))
                sum += i;
        }
        printf("sum=%d\n", sum);
        return 0;
    }

方法3：

#include<stdio.h>
    
    int IsPrime(int n)
    {
       //判断n是否为质数，如果是返回1，否则返回0
        int i;
        for (i = 2; i * i <= n; i++)//这个地方的遍历范围是【2，sqrt(n)】，这里不想用开根号，所以改成了i * i <= n
        {
            if (n % i == 0)
                return 0;
        }
        return 1;
    }
    
    int main()
    {
        int i, nUpLimit, sum = 0;
        printf("输入一个正整数,下面将求出这个范围内的质数和: ");
        scanf_s("%d", &nUpLimit);
        for (i = 2; i <= nUpLimit; i++)
        {
            if (IsPrime(i))
                sum += i;
        }
        printf("sum=%d\n", sum);
        return 0;
    }

方法4：  
通过筛选法，排除所有非素数，并做好标记。

参考代码：

#include <stdio.h>
    #include <malloc.h>
    
    void FilterPrimer(char* pIsPrime, int n)
    {
       //使用筛选法过滤掉不是质数的，这种是求某个范围内所有质数最快的方法，时间复杂度均摊是线性的
        int i, j;
        for (i = 2; i <= n; i++)
            pIsPrime[i] = 1;//先假定所有的数都是质数
    
        for (i = 2; i <= n; i++)
        {
            if (pIsPrime[i])
            {
       //如果某个数是质数，则把它的倍数全部过滤掉
                for (j = 2; j * i <= n; j++)
                    pIsPrime[j * i] = 0;
            }
        }
    }
    
    int main()
    {
        int i, n, sum = 0;
        printf("输入求和的最大项数: ");
        scanf_s("%d", &n);
        char *pIsPrime = (char*)malloc((n + 1) * sizeof(char));
        FilterPrimer(pIsPrime, n);
        for (i = 2; i <= n; i++)
        {
            if (pIsPrime[i])
            {
                sum += i;
            }
        }
        printf("sum=%d\n", sum);
        return 0;
    }

运行结果：  
![这里写图片描述][SouthEast]

[SouthEast]: /images/20220616/41e9475ed6864bf68f253d810567c6e0.png