paizaラーニング レベルアップ問題集 Aランクレベルアップメニュー JavaScript 素数判定

素数判定 (paizaランク C 相当)

JavaScriptで解いてみました。

解答例

Nの条件が1 ≦ N ≦ 10 ^ 10なので、ふつうに、Nが、2からN-1まで、割り切れるか調べると、タイムオーバする可能性があります。
数学的な証明は省きますが、N-1まで調べなくても、Nの0.5乗(ルートN)の整数まで調べればOKです。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const N = Number(lines[0]);

//Nが１ならば素数でない
if (N === 1) {
    console.log("NO");
//nが２ならば素数    
} else if (N === 2) {
    console.log("YES");
//それ以上の時    
} else {
    //2で割り切れたら4以上の偶数なので素数ではない
    if (N % 2 === 0 ) {
        console.log("NO");
    } else {
        //3以上の奇数で割り切れるか
        for (let i = 3; i <= Math.sqrt(N); i += 2) { //ルートNまででOK
            //割りきれたら素数ではない
            if (N % i === 0) {
                console.log("NO");
                break;
            }
            //最後までいったら素数
            if (i + 2 > Math.sqrt(N)) {
                console.log("YES");
            }
        } //for

    } //if N%2
       
} //if N=1,2

解答例(C++の場合参考)

N が素数である場合に is_prime が true に、素数でない場合に false にします。
N が 1 である場合には、例外的に is_prime を false にしています。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const n = Number(lines[0]);

let is_prime = true;//素数判定

if (n == 1) {
    is_prime = false;
}

for (let i = 2; i * i <= n; i++) {
  if (n % i == 0) {
    is_prime = false;
  }
}

if (is_prime) {
  console.log("YES");
} else {
  console.log("NO");
}

解答例(Python3の場合参考)

N が素数である場合に is_prime が true に、素数でない場合に false にします。
N が 1 である場合には、例外的に is_prime を false にしています。

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin", "utf-8").trim();
const lines = input.split("\n");

const N = Number(lines[0]);

let is_prime = true;//素数判定

if (N == 1) {
    is_prime = false;
}

for (let i = 2; i <= N**0.5; i++) { //Nの0.5乗まででOK
  if (N % i == 0) {
    is_prime = false;
  }
}

if (is_prime) {
  console.log("YES");
} else {
  console.log("NO");
}