[programmers/CodingTest/Python]小数点を検索(レベル1)

3233 ワード
coding test python programmers テキストリンク

問題の説明


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

せいげんじょうけん

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

    • I/O例

    n	result
10	4
5	3

    I/O例説明


    I/O例#1
    1から10の間の小数は[2,3,5,7]の4個であるため,4を返す.
    I/O例#2
    1から5の間の小数は3を返します.[2,3,5]の3つがあるからです.

    方法


    最初に1からnの間で所定の数を遍歴し,iを2からint(sqrt(i)に分け,分離がある場合はカウントしないようにコードを記述する.テストケースと精度テストはすべて合格したが、効率的には合格しなかった.
    そこで에라토스테네스의 체を使用することにした.에라토스테네스의 체を用いて素数を求める方法が最も速いことが分かった.에라토스테네스의 체の原理は以下の通りである.
  • 小数の配列chkをチェックします.
  • 2からnを巡り、chk[i]に小数点チェックがない場合、chkはiの倍数をインデックスとする要素を小数点としてチェックする.
  • chk配列は小数と表記された数字を出力する.
    • この方式を用いてコードを実現した.
  • はfalse*(n+1)として宣言され、少数の判別検査のための配列chkである.
  • 2からnツアーまでのiにご挨拶をお伝えします.
    ->chk[i]がfalseの場合、
    -->一時変数idxを宣言し、i*2を入れます.
    -->idxがn以下の場合、while文を繰り返します.
    -->chk[idx]がTrueに更新されました.
    ----->idx増加i.
    • 正解
  • の変数回答を保存し、chk의 False개수-2を保存すると発表した.(2を使用する理由は、chkが0度と1度のFalseを格納し、0と1が小数ではないためです.)
  • の答えを返します.

    • solution.py

    def solution(n):
    chk=[False]*(n+1)
    for i in range(2, n+1):
        if not chk[i]:
            idx=i*2
            while idx<=n:
                chk[idx]=True
                idx+=i
    answer=chk.count(False)-2
    return answer
    Androidアプリ開発のための、Android端末の開発者モード設定方法
    [テストエンコーディング]JavaScript#1