题解 | Forsaken喜欢数论

import java.util.*;

public class Main{
    static final int N = 30000005;
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long ans = 0;
        boolean[] isprime = new boolean[N];
        int[] prime = new int[N];
        int cnt = 0;
        for(int i=1;i<=n;i++) isprime[i] = true;
        isprime[0] = isprime[1] = false;
        for(int i=2;i<=n;i++){
            if(isprime[i]){
                ans += i;
                prime[++cnt] = i;
            }
            for(int j=1;j<=cnt && i*prime[j] <= n;j++){
                if(isprime[i*prime[j]]) ans += prime[j];
                isprime[i*prime[j]] = false;
                if(i%prime[j] == 0) break;
            }
        }
        System.out.print(ans);
    }
}