[yukicoder] No.36 素数が嫌い！ - ヤマカサのプログラミング勉強日記

素数判定を行う問題

No.36 素数が嫌い！ - yukicoder

どのようにして解けばよいか分からなかったので、解説サイトを見ました。

解説サイト

sugarknri.hatenablog.com

yukicoder No.36 - 素数が嫌い！ - ゲームにっき（仮）別館（仮）

考え方

解説サイトを見ると、素因数の数を求めれば良いみたいです。素因数の数を求めるためには、素数判定を行えば良いことが分かります。与えられる数が非常に大きいので、工夫して素数判定を行わなければいけません。

目標

$1$ と $N$ を除いた数のなかで、素因数の数が2以上となればYESを出力します。そうでなければ、NOを出力します。

szarny.hatenablog.com

上記のサイトによると、素数を判定する数の上限は、 $\sqrt{N}$ です。また、上限は $\sqrt{N}$ を含まないで考えます。これは、素数の平方数と立方数を考えるときに必要になります。

素因数を数えるときの注意点として、 $2 \leq i \lt \sqrt{N}$ を満たす $i$ に対して、 $N \mod i^2 = 0$ となる $i$ はカウントを2にします。

ここで、素数を $p$ とします。

$N = p^2$ のとき約数は、 $1, p, N$ となります。これはNOとなります。
$N = p^3$ のとき約数は、 $1, p, p^2, N$ となり、 $p^2$ は素数ではないので、YESとなります。

$2 \leq i \lt \sqrt{N}$ の範囲では、

$2 \leq i \lt \sqrt{N} = p \sqrt{p} \lt p^2$

となってしまいます。したがって、 $N \mod i^2$ を調べる必要がありました。

コード

import java.util.Scanner;

public class Exec0036 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long N = scan.nextLong();
        scan.close();
        if(N < 7) {
            System.out.println("NO");
        }else {
            if(numPrime(N) >= 2) {
                System.out.println("YES");
            }else {
                System.out.println("NO");
            }
        }

    }
    public static int numPrime(long n) {
        int cnt = 0;
        for(long i = 2; i < (int)Math.sqrt(n); i++){
            if(n % i == 0) {
                cnt ++;
                if(n % (i * i) == 0) {
                    cnt ++;
                }
            }
        }

        return cnt;
    }
}

感想

こういう問題は苦手です。僕も素数嫌い。