山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[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;
    }
}

感想

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