[伯俊]JavaScript 1978号小数点を検索

7073 ワード
boj テキストリンク

Question


[伯俊]JavaScript 1978号小数点を検索

input


1行目の数字はNです.Nは100以下である.次はN個、数は1000以下の自然数です.

output


与えられた数のうちの少数の数を出力します.

example

4
1 3 5 7
3

ソリューション1(最も基本的な方法)


2から判別する数に分ける前に、残りの数が0未満であれば少数と判定します.
すべての関連数字を確認する必要があるため,時間的複雑度はO(N)である.
console.log(require('fs').readFileSync('/dev/stdin').toString().trim().split(/\s+/).slice(1).map(Number).filter(x=>{
    if(x===1) return;
    for(let i=2;i<x;i++){
        if(x%i===0) return;
    }
    return true;
}).length)

ソリューション2(改善された方法)


この数字√Nのみを確認する方法です.例えば、80の約数は以下のようになります.

√80の価格は約8です.xxで表され、この値は約数の中間値である.この原理を用いて2から√Nの値をチェックすると,以降の値は再確認する必要がなくなり,時間的複雑度はO(√N)となる.
コードの可読性のために、Math.sqrt(x)ではなくiの二乗値を決定する.
console.log(require('fs').readFileSync('/dev/stdin').toString().trim().split(/\s+/).slice(1).map(Number).filter(x=>{
    if(x===1) return;
    for(let i=2;i*i<=x;i++){
        if(x%i===0) return;
    }
    return true;
}).length)

Reference


https://myjamong.tistory.com/139
アクセルシミュレーション試験6話
ビッグデータ解析記事で終了(ディレクトリ)