問題 B: 素數處理

時間限制: 1 Sec   記憶體限制: 128 MB

送出: 226   解決: 11

[ 送出][ 狀态][ 讨論版]

題目描述

最近，聰明的二哈喜歡上了數學，迷上了素數。經過一番折騰，研究出了二哈素數大猜想，可以輕松求出任意區間[l,r]之間素數和。二哈希望你能編寫個代碼幫他求解任意a，b之間的所有素數和，進而驗證他的猜想

輸入

一行，a b(0<=a,b<=2000000) （資料範圍剛才給小了，由 0<=a,b<=200000改為 0<=a,b<=2000000 ，十分抱歉）

輸出

一行，a,b之間（含a，b）所有素數的和。

樣例輸入

3 5      

樣例輸出

8 題意： 是求一段範圍内的素數之和，此題範圍太大，如果用原來的暴力周遊方法的話，時間會花費很多，是以用素數删選法對資料進行處理 素數删選法：  找到一個素數，就将此素數的所有倍數全部删掉

#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
int a[2000000];
int prime(){
	int i,j;
	for(i=2;i<=sqrt(2000005);i++){
		if(a[i]==0){
			for(j=i*i;j<=2000005;j+=i){
				a[j]=1;//素數篩選法 
			}
		}
	}
}

int main(){
	int l,r;
	memset(a,0,sizeof(0));
	a[1]=1;
	prime();
	while(cin>>l>>r){
		if(r<l)swap(l,r);//判斷确定輸入兩值從小到大 
		int i;
		long long sum=0;
		 
	for(i=l;i<=r;i++){
		if(a[i]==0){
			sum+=i;
		}
	}
	cout<<sum<<endl;
	}
	
}