质数的幂

只要找到一个质数，就从它的2次幂往答案里面加就行了，只要幂值不超过n：

import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception{
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Set<Integer> r = new HashSet<>();
        for(int i = 2; i <= n; ++i){
            if(f(i)){
                r.add(i);
                for(int j = 2;; ++j){
                    int p = (int)Math.pow(i, j);
                    if(p > n) break;
                    r.add(p);
                }
            }
        }
        System.out.println(r.size());
    }
    static boolean f(int n){    //暴力筛质数
        if(n <= 1) return false;
        if(n == 2) return true;
        for(int i = 2; i < n; ++i){
            if(n%i == 0) return false;
        }
        return true;
    }
}