Description

编写程序，统计给定整数M和N区间内素数的个数并对它们求和。

Input

两个正整数M和N（1≤M ≤ N ≤ 10000）。

Output

在一行中顺序输出M和N区间内素数的个数以及它们的和，数字间以1个空格分隔。

Sample Input 1 

10 31

Sample Output 1

7 143

方法一：用到了数学上的一些结论

#include <stdio.h>
#include<math.h>
int sushu(int k);

int main()
{
    int m,n,sum=0,count=0;
    scanf("%d %d",&m,&n);
    for(int i=m;i<=n;i++)
    {
        if(sushu(i))
        {
            sum=sum+i;
            count++;
        }
    }
    printf("%d %d",count,sum);
    return 0;
}

int sushu(int k)
{
    if(k==1||k==4)
        return 0;
    if(k==2||k==3)
        return 1;
    if(k%6!=1&&k%6!=5)
        return 0;
    else
    {
        for(int i=5;i<sqrt(k)+1;i+=6)
        {
            if(k%i==0||k%(i+2)==0)
            return 0;
        }
        return 1;
    }
}

方法二：用数组。两个数相乘得到的数的位置被置0，剩下的值为1的都是素数

#include <stdio.h>
#include<string.h>
int main()
{	int a,b,i,prime[10001],sum=0,cnt=0;
	scanf("%d%d",&a,&b);
	memset(prime,1,sizeof(prime));
	prime[1]=0;
	for(i=2;i<10001;i++)
	{	if(prime[i])
		{
			for(int x=2;x*i<10001;x++)
				prime[i*x]=0;
		}
	}
	for(i=a;i<=b;i++)
	{	if(prime[i])
		{	sum+=i;
			cnt++;
		}

	}
	printf("%d %d",cnt,sum);
	return 0;
}