C 解法, 执行用时: 75ms, 内存消耗: 16952K, 提交时间: 2023-03-09 09:04:50

#include<stdio.h>
int main()
{
    long long int t,i,sum=0,j,l,r,cnt=0;
    long long int a[1000001]={0},b[1000001];
    for(i=2;i<1000001;i++)
    {
        if(a[i]==0)
        {
            cnt+=i;
            for(j=i*2;j<1000001;j+=i)
                a[j]=1;
        }
        b[i]=cnt;
    }
    scanf("%lld",&t);
    for(i=0;i<t;i++)
    {
        scanf("%lld %lld",&l,&r);
        printf("%lld\n",b[r]-b[l-1]);
    }
    return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 695ms, 内存消耗: 64988K, 提交时间: 2022-12-28 20:35:37

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+6;
bool p[N];
map<int,int>mp;
signed main()
{
   int cnt=0;
   for(int i=2;i<N;i++)
   {
       if(p[i]==0)
       {
           cnt+=i;
           for(int j=i+i;j<N;j+=i)
               p[j]=1;
       }
       mp[i]=cnt;
   }
    int tt;
    for(cin>>tt;tt--;)
    {
        int l,r;
        cin>>l>>r;
        cout<<mp[r]-mp[l-1]<<'\n';
    }
}

C++(clang++ 11.0.1) 解法, 执行用时: 606ms, 内存消耗: 9172K, 提交时间: 2023-04-13 22:31:28

#include<bits/stdc++.h>
using namespace std;
long long check(int x)
{
    if(x<2)
        return 0;
    for(int i=2;i*i<=x;i++)
        if(x%i==0)
            return 0;
    return x;
}
int main()
{
    long long a[1000005]={0,0};
    for(int i=2;i<=1000000;i++)
    a[i]=a[i-1]+check(i);
    int t;
    cin>>t;
    while(t--)
    {
        int l,r;
        cin>>l>>r;
        cout<<a[r]-a[l-1]<<'\n';
    }
    return 0;
}