【アルゴリズムの問題を解く】【Python】白駿1929号:小数点を探す

4687 ワード
エラトステネスのふるい パイ 白駿 小数を求める 1929日 テキストリンク

白駿1978題リンク:https://www.acmicpc.net/problem/1978


📑 問題の説明


与えられた2つの数の間のすべての小数を求めるプログラムを作成します.
入力:2つの数
出力:指定した2つの数の間のすべての小数点

💡 トラブルシューティング方法


接着剤を解く前に、「エラトニスのふるい」の説明を見てからコードすることをお勧めします.
エラトネスのふるいは,与えられた数をリストした後,2の倍数を繰り返し除去し,3の倍数を除去し,小数を探す方法である.
0から100000までの長さのリストにします.小数であればTrue、小数でなければFalse、最後にTrueインデックスのみを出力します.
最初のコードは
2からn(2つの数の中で最大の数)まで繰り返します.
index=2の場合、3からnを2で割った場合にのみ、残りのindex値をfalseにしようとしますが、「タイムアウト」が発生します.
したがって、残りの演算を使用するのは誤った方法ではありませんが、乗算を使用すると、
index=2の場合、2(n未満の数)<=nの場合、[2](n未満の数)indexをfalseとすると、より短い時間で小数を求めることができる.

💻 コード#コード#

import sys


def find_pn(m, n):
    tf_list = [True for i in range(1000001)]
    tf_list[0] = False
    tf_list[1] = False

    for i in range(2, n):
        j = 2
        while(j * i <= n):
            tf_list[j * i] = False
            j += 1


    for i in range(m, n + 1):
        if (tf_list[i] == True):
            print(i)
    return


if __name__ == '__main__':
    m, n = map(int, sys.stdin.readline().split())
    result = find_pn(m, n)

💟 詳細

[python]白駿15724州指数(DP)
ファイルブラウズ+ファイル選択