- Ta xét thấy giới hạn $1 \le n \le 10^8$ vừa đủ dể dùng lặp đến `sqrt n`, và loại bỏ số chẵn thì khá tối ưu thời gian `O(nlog log n)`

`1.n<=10^8` nên biến tong dùng long  phù hợp giới hạn

`2.` Số chẵn là hợp số `=>` loại bỏ (dùng ánh xạ để loại bỏ trực tiếp)

`3.` Bool lưu đúng/ sai `->`tốn `1` byte `->` bitset tốn 1 bit (`1` bit `=1/8` byte)

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        if (n < 2) {
            System.out.println(0);
            return;
        }
        BitSet Comps = new BitSet(n / 2 + 1);
        long sum = 2;
        int sqrtN = (int) Math.sqrt(n);
        for (int i = 3; i <= sqrtN; i += 2) {
            if (!Comps.get(i / 2)) {
                sum += i;
                for (int j = i * i; j <= n; j += 2 * i) Comps.set(j / 2);
            }
        }
        int begin = (sqrtN % 2 == 0) ? sqrtN + 1 : sqrtN + 2;
        for (int i = begin; i <= n; i += 2)
            if (!Comps.get(i / 2)) sum += i;
        System.out.println(sum);
    }
}