蓝桥杯算法提高VIP-素数求和 （C语言代码）线性筛选

解题思路:

注意事项:

参考代码:

#include <stdlib.h>

#include <stdio.h>

#include <string.h>

#include <math.h>

#define maxm 2000010

int prime[maxm];

int s[maxm];

void Prime(int n)//求n以内的素数

{

   int i,k,t;

   for (i=2;i<=n;i+=2) s[i]=0; //所有的偶数不可能为素数　赋值为０

   for (i=1;i<=n;i+=2) s[i]=1; //所有奇数先赋值为1

   s[1]=0; s[2]=1;

   for (i=3;i<=sqrt(n);i+=2)

   {

       if (s[i])

   {

          //应为所有偶数已经剔除，所以此处t=3*i（相当于）也就是此次剔除的仍是奇数，所以避免了重复剔除偶数，速度快。

          t=3*i;

          while (t<= n)

  {

             s[t]=0;

             t=t+2*i; //奇数加偶数为奇数 奇数加奇数为偶数 所以加2i为奇数 避免重复剔除偶数

  }

   }

   }

   k=1; prime[1]=2;

   for (i=3;i<=n;i+=2)

   {

         if (s[i]==1) { k++; prime[k]=i; }

   }

   prime[0]=k; //p[0]为1到n之间多少个素数

}

int main()

{

    int  i, n;

    unsigned long long sum = 0;

scanf("%d", &n);

Prime(n);

for(i = 1; i <= prime[0]; i++)

{

          sum += prime[i];

}

printf("%llu", sum);

return 0;

}