yukicoder No.36 素数が嫌い！ 解説

問題文

解説

今回は、与えられた数が素数かどうかの判定ではない。合成数を約数に持つかの判定だ。謎のWAを出している人はまずここを読み間違えていないか確認しておこう。
そのうえで、解説を書く。
まず、素数判定については以下の方法でできる。
ある数$N$が素数かどうかの判定は、$\sqrt{N}$までで割り切れるかどうかの判定でできる。
では、合成数の約数を持つかの判定はどうするか。
例えば、ある数$i$が$N$に割り切れたとする。
$i$が合成数かどうかの判定も$\sqrt{i}$までで割り切れるかどうかの判定をする。
もし割り切れた数があったなら、$i$は合成数なので$N$は条件を満たす数になる。

C++での解答例

#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int main(){
  ll n;cin>>n;
  for(ll i=2;i*i<=n;i++){
    if(n%i!=0)continue;
    bool ok=false;
    for(ll j=2;j*j<=i;j++)
      if(i%j==0){
        ok=true;
        break;
      }
    for(ll j=2;j*j<=n/i;j++)
      if((n/i)%j==0){
        ok=true;
        break;
      }
    if(ok){
      cout<<"YES\n";
      return 0;
    }
  }
  cout<<"NO\n";
}