2012年8月28日星期二

Sieve of Eratosthenes

看完這篇文章後,用Python implement Sieve of Erathosthenes。在網上搜尋一下,發現一個十分適合的module bitarray,適合用來儲存非常大的boolean array,好過用list,但又唔想安裝extra module,於是用built-in array。

import array

def eratostheenes_sieve(n):
    '''Return array of boolean that the index is prime or not.

    >>> eratostheenes_sieve(100).count(True)
    25
    >>> eratostheenes_sieve(1000).count(True)
    168
    >>> eratostheenes_sieve(10000).count(True)
    1229
    >>> eratostheenes_sieve(100000).count(True)
    9592
    >>> eratostheenes_sieve(1000000).count(True)
    78498
    '''
    a = array.array('b', [False, False] + [True] * (n - 1))
    for i in range(2, math.ceil(math.sqrt(n))):
        if a[i]:
            for j in range(i * i, n + 1, i):
                a[j] = False
    return a

這個project primesieve提供Sieve of Erathosthenes C++ optimize版本,值得參考。至於Sieve of Atkin,還未明瞭當中原理,理解後再另文探討。

沒有留言:

發佈留言