统计素数并求和(大数据)

统计素数并求和(大数据),第1张

统计素数求和(大数据)

本题要求统计给定整数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< 

 

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5709208.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存