#include<iostream> #include<algorithm> #include<string.h> using namespace std; typedef long long ll; const int MAX=70000; bool visit[MAX]; int prime[MAX]; ll f[MAX]; void sieve(int n){ int cnt=0; visit[0]=true;visit[1]=true; memset(visit,false,sizeof(visit)); for(int i=2;i<=n;++i){ if(!visit[i])prime[cnt++]=i; for(int j=0;j<cnt;++j){ if(i*prime[j]>n)break; visit[i*prime[j]]=true; if(i%prime[j]==0)break; } } } void Sum(int n){ int pos=0; f[0]=0;f[1]=0; for(int i=2;i<=n;++i){ if(prime[pos]>i)f[i]=f[i-1]; else{f[i]=f[i-1]+prime[pos++];} } } int main() { sieve(MAX); Sum(MAX); int left,right; while(cin>>left>>right){ if(left>=right)swap(left,right); ll sum=f[right]-f[left]; //cout<<f[right]<<" "<<f[left]<<endl; if(!visit[right]&&right!=1)sum-=right; //if(is_prime[left])sum-=left; cout<<sum<<endl; } return 0; } |
Double click to view unformatted code.