题解 | #T2#

对于这一题，我们先用线性筛处理每一个质数，两个质数中的合数肯定是前一半是连小的，后一半联大的。然后由于1到x的和是x*(x+1)/2，两个加起来就是x*(x+1)。值得注意的是：最后会有一部分没处理，需要补全。

贴代码：

#include<bits/stdc++.h>
using namespace std;
bool st[10000030];
int primes[700030],cha[700030];
int primes_sum(int x){
    int cnt=0;
    for(int i=2;i<=x;i++){
        if(!st[i]){
            primes[cnt++]=i;
        }
        for(int j=0;j<cnt && primes[j]*i<=x;j++){
            st[primes[j]*i]=1;
            if(i%primes[j]==0) break;
        }
    }
    return cnt;
}
int main(){
    int n;
    cin>>n;
    int cnt=primes_sum(n);
    int sum=2;
    for(int i=2;i<cnt;i++){
        int nn=(primes[i]-primes[i-1])/2;
        sum+=nn*(nn+1);
    }
    cout<<sum+(n-primes[cnt-1])*(n-primes[cnt-1]+1)/2;
}