[浄水論]エラトスのふるい

5683 ワード
コンピュータエンジニアリング テキストリンク
出典:[これがコードテスト]本
  • では、テストステロンの体はO(Nx logn)時間であり、線形時間内に運動できるほど速い.
  • このBC 274年生まれの人は、どう思いますか
  • Pythonコードでエラトネスのボディを実現しました.

    • 少数の判別

  • 小数とは、2より大きい自然数のうち、1と自分以外を区別しない自然数をいう.
    • 記述コード
  • はO(X^1/2)で小数を判別できる.
    Xを判別しないで、Xの平方根を検査するだけです.
    • import math
def is_prime_number(x):
    if x == 1 : return False
    for i in range(2, int(math.sqrt(x))+1):
        if x % i == 0: return False
    return True

print(is_prime_number(4))
print(is_prime_number(11))
    結果:False/True

    エラトステネスのふるい


  • 上のコードはO(X^1/2)時間の複雑さで効率的です.例えば、判別数が100,000程度であれば、演算により1000回以下の値を見つけることができる.

  • しかし、1つの数に対して、小数であることを判別する必要がない場合ではなく、1つの数の範囲を与えた場合、その整数の範囲内に存在するすべての小数が見つかった場合、どうなるのでしょうか.

  • テストステロンアルゴリズムは、複数の数が素数であるか否かを判別する際に用いられる代表的なアルゴリズムである.
  • エラス菌体コード
    • import math
n = 100
array = [True for i in range(n+1)]
array[0], array[1] = False, False

for i in range(2, int(math.sqrt(n))+1):
    x = 2
    while i * x <= n:
        array[i*x] = False
        x += 1

for i in range(50,60):
    print(i,':',array[i])
    結果:53、59から真/偽
    Github 4 - issue tracker (+ workFlow)
    FLEXとJSPのハイブリッドアプリケーションの実装方法