Sieve-of-Eratosthenes タグの一覧です(1 件)

[Python]剰余算の真理値判定とエラトステネスの篩

例えばこのような奇数を求めるコードがあって

In [1]: list(filter(lambda x: x % 2, range(10)))
Out[1]: [1, 3, 5, 7, 9]

このなかの x % 2 は真理値判定となっていて、余りがあればTrueであり、なければFalseである。ところが(俺だけかもしれないが)これがどうもしっくりこない(笑)% は余りを求めるのだから、余りがあればTrueなんだということは頭では理解しているつもりなのだけど、余りがゼロの場合に割り切れたんだからTrueだ、とふと思ってしまう。なんでだろうとずっと考えていたのだけれど、どうやら俺は奇数より偶数のほうが好きだからかもしれない。。

# -*- coding: utf-8 -*-

def sieve(num):
    primes = list(range(3, num, 2))
    for i in range(len(primes)):
        if primes[i]**2 > primes[-1]: break
        primes[i+1:] = filter(lambda p: p % primes[i], primes[i+1:])
    print(primes)

if __name__ == '__main__':
    import sys
    sieve(int(sys.argv[1]))

上記コードにも偶数をフィルタリングして除外する箇所があって、そこでも剰余算の真理値判定をしている。これはエラトステネスの篩という有名なアルゴリズムらしい。

良いもの。悪いもの。: アルゴリズムの素晴らしさに気付かせてくれたのはエラトステネスの篩だった
こちらのサイトのコードを Python3で書き直させてもらった。


PAGE TOP