View Code of Problem 27

#include<iostream>
using namespace std;
typedef long long ll;
const int MAX=70000;
bool visit[MAX];
int prime[MAX];
bool is_prime[MAX];
ll f[MAX];
void sieve(int n){
    int cnt=0;
    is_prime[0]=false;is_prime[1]=false;
    for(int i=2;i<=n;++i){
        if(!visit[i]){prime[cnt++]=i;is_prime[i]=true;}
        for(int j=0;i*prime[j]<=n;++j){
            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){
        ll sum=f[right]-f[left];
        //cout<<f[right]<<" "<<f[left]<<endl;
        if(is_prime[right])sum-=right;
        //if(is_prime[left])sum-=left;
        cout<<sum<<endl;
	}
	return 0;
}