- Sử dụng sàng nguyên tố cho tới n, sau đó đếm số lượng và tổng các số nguyên tố đó

` ->` Độ phức tạp là O(n log(n))

code:
#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    
    int prime[n+1];
    for (int i=0; i<=n; i++) prime[i]=1;
    
    for (int i=2; i*i<=n; i++) {
        if (prime[i]) {
            for (int j=i*i; j<=n; j+=i) {
                prime[j]=0;
                // cout << j << " - ";
            }
        }
    }
    
    int cnt=0, sum = 0;
    for (int i=2; i<=n; i++) if (prime[i]) cnt++,sum+=i;
    cout << cnt << endl << sum << endl;
    for (int i=2; i<=n; i++) if (prime[i]) cout << i << " ";
    
}

\begin{array}{c} \color{#db1616}{\texttt{#Khoadang09}} \end{array}

#include <bits/stdc++.h>
using namespace std;
int main(){
    vector <int> pr(1e6+1,1);
    pr[0] = pr[1] = 0;
    for (int i=2; i<=1e6; i++)
        if (pr[i]) 
            for (int j=i+i; j<1e6; j+=i)
                pr[j] = 0;
    int n; cin >> n;
    int d = 0, s = 0;
    for (int i=2;i<n;i++)
        if (pr[i]){
            d ++;
            s += i;
        }
    cout << d << "\n" << s << "\n";
    for (int i=2;i<=n;i++)
        if (pr[i]) cout << i << " ";
    return 0;
}