yukicoder No.36 素数が嫌い！

今日もyukicoder

問題

yukicoder.me

入力で与えられた数が「素数,1,使う数自身」以外で割り切れるかどうかを判定する。

考え方

1はダメ。素数もダメ，入力で与えられた数Nもダメ。それ以外の数字で割り切れればＯＫということなので，合成数の約数を持つかどうかを調べなさいということ。

• 合成数とは，自然数であって，1とその数自身以外の約数を持つ数のこと。

もう少しかみ砕けば，素数ではない自然数のことである。 合成数を約数に持つということは という形に素因数分解できるということである（各 は素数）。

従って，与えれらたNが2個以上の素数を約数として持つかどうかを調べればよい。

実装

通常の素数判定のコードは以下の数でNを割り切るものが1個もなければNは素数，そうでなければ素数でない（合成数）という処理なので，これを少しいじって，Nを割り切る数が2個以上あるかどうかの判定をするようにした。

#1,素数，自分自身以外で2つの約数を持つか
def hasTwoDivisor(N):
    cnt = 0
    if N == 1:
        return False
    elif N == 2:
        return False
    else:
        i = 2
        while N >= i*i:
            if N%i == 0:
                cnt += 1
                N //= i
                continue #iで割り切れたときは，同じ数でもう一度試す
            i += 1
        return cnt >=2
    return False
N = int(input())
if hasTwoDivisor(N):
    print("YES")
else:
    print("NO")