[プログラマー]小数点を検索するJavaScriptアルゴリズム

4618 ワード
アルゴリズム#アルゴリズム# JavaScript プログラマ 小数点を検索 テキストリンク

[プログラマー]小数点を検索するJavaScriptアルゴリズム


https://programmers.co.kr/learn/courses/30/lessons/12921

Q.小数点を探す


1から入力した数字nまでの小数を返す関数を作成します.
小数は1とそれ自体の数です.
(1は小数ではありません.)

せいげんじょうけん

  • nは2以上100000以下の自然数です.

    • I/O例


    nresult10453

    I/O例説明


    I/O例#1
    1から10の間の小数は[2,3,5,7]の4個であるため,4を返す.
    I/O例#2
    1から5の間の小数は3を返します.[2,3,5]の3つがあるからです.
  • コード
    • function solution(n) {
    var arr = new Array(n+1).fill(true);     // 배열 만들어서 true 채우기 
    var end = Math.sqrt(n); 
    var cnt = 0;
    for(let i =2; i <=end; i++){		// i*i가 n보다 크면 안됨
        if(arr[i]===false) continue;     // 이미 소수인건 뛰어넘기 
        for(let k= i*i; k<=n; k+=i){    // 소수가 아닌 데이터는 false
            arr[k]=false;				// i의 제곱과 배수들은 i로 나누어떨어지기 때문에 소수가 아님
        }
    }
    for(let i =2; i<=n; i++){
        if(arr[i]===true) cnt ++
    }
   
    return cnt
}
    BJ 1753最短経路
    Flatten, Unflatten