Giúp mình với, dùng C++ nha An được thầy giáo Thuận cho 2 số nguyên a, b (1 <= a <= b <= 5.10^7). Vì là một học sinh chuyên toán - tin nên An có thể tìm được tất cả các số nguyên tố trong đoạn [a, b] trong chưa đầy 1s. Vì vậy thầy Thuận đã nhờ An tìm giúp tổng các số nguyên tố từ a đến b. Nhưng do An vẫn đang đi du lịch nên An đã nhờ bạn tìm giúp. Input: Gồm hai số nguyên a, b Output: Tổng các số nguyên tố trong đoạn [a, b] Ví dụ: Nhập: 1 4 Xuất: 5

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define ll long long

using namespace std;
const ll nmax = 5*1e7 + 5;

bool f[nmax+7];
void sangnt() 
{
    memset(f, true, sizeof(f)); 
    f[0] = f[1] = false;
    for (int i = 2; i * i <= nmax; i++)
    {
        if (f[i])
            for (int j = i * i; j <= nmax; j += i) 
                f[j] = false;
    }
}

int main()
{
    sangnt();
    ll a,b,s=0;
    cin>>a>>b;
    for(int i=a;i<=b;i++)
    {
        if(f[i]) s+=i;
    }
    cout<<s;
}

Đây là một bài sử dụng sàng nguyên tố Eratosthenes để nhanh chóng tìm ra tất cả các số nguyên tố trong khoảng $\left[l, r \right]$. Độ phức tạp của thuật toán này là $O(r \text{ log log } r)$, đủ tốt để chạy trong 1s sử dụng một số cách tối ưu hóa bằng pragma.

Tuy nhiên, lưu ý rằng, trong các kỳ thi, việc sử dụng pragma là không được phép.

Code (C++, chạy trong $\approx 500$ ms khi $(l,r)=(1,5\times 10^7)$)

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e7+5;

bool notPrime[maxn];
long long l,r,ans;

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    notPrime[1] = true;
    cin >> l >> r;
    for(long long i=2;i<=r;i++){
        if(!notPrime[i]){
            // i la so nguyen to
            if(i >= l) ans += i;
            for(long long j=i*i;j<=r;j+=i) notPrime[j] = true;
        }
    }
    cout << ans;
    return 0;
}