C - Unexpressed

問題

atcoder.jp

これは解きたかったなぁ、、
素朴に素因数分解を1-NまでやってるとTLEになるのは当たり前なんですが、
割っていく問題ではなく、二乗できるかどうか、なのでi*iの値がNより小さいか同値であればそれはNGの数字としちゃっていいんですよね。
なので最終的には総数からNGの総数を引けばそれが答えになります。

注意

ArrayListを使うとNGになります。
もちろん、答えは重複する可能性があるので、Setを使用している感じです。

package AtCoder.ABC193;
import java.util.*;
public class MainC {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        sc.close();
        Set<Long> nums = new HashSet<>();
        for(long i=2; i*i<=n; i++) {
            long tmp = i*i;
            while(tmp <= n) {
                nums.add(tmp);
                tmp *= i;
            }
        }
        System.out.println(n - nums.size());
    }
}