统计素数并求和（大数据）

统计素数并求和（大数据）

本题要求统计给定整数M和N区间内素数的个数并对他们求和。

输入格式:

第一行输入一个T；

接下来T行，每行输入两个数，分别代表M和N。（1 <= T, M, N <= 1000000）

输出格式:

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

样例">输入样例:

2
1 5
5 10

输出样例:

3 10
2 12

#include 
#define N 1000010
using namespace std;
long long f_1[N],f_2[N];
int a[1001110]={0};
void id(int m)
{
	a[0]=a[1]=1;
	for(int i=2;i<=m;++i){
		if(!a[i]){
			for(int j=i*2;j<=m;j+=i) a[j]=1;  //埃氏筛法
		}
	}
	long long t=0,s=0;
	for(int i=0;i<=m;++i){           //前缀和
		if(!a[i]){
			++t;
			f_1[i]=t;
			s+=i;
			f_2[i]=s;
		}else{
			f_1[i]=t;
			f_2[i]=s;
		}
	}
	
}
int id_1(int n,int m)
{
	long long t=0,s=0;
	t=f_1[m]-f_1[n-1];
	s=f_2[m]-f_2[n-1];
	printf("%lld %lldn",t,s);
	//cout< 
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: https://outofmemory.cn/zaji/5709208.html