غربال اراتستن

غربال اراتستن به طور کلی برای محاسبه اول بودن یا نبودن اعداد طبیعی کمتر از n به کار می‌رود. این روش به این صورت است که ابتدا فرض می‌کنیم تمام اعداد بین ۲ تا n همگی اول هستند. سپس با شروع از دو هر بار که به عددی اول می‌رسیم مطمئن می‌شویم که مضارب آن اول نیستند و با حرکت بر روی مضارب آن, آن‌ها را از اول بودن در می‌آوریم.

sieve.py

def sieve(n): # n must be greater than 1
    is_prime = [True] * n
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n):
        if is_prime[i]:
            for j in range(2 * i, n, i):
                is_prime[j] = False
    return is_prime

زمان اجرای کد بالا برابر $n\sum_{p}\frac{1}{p}$ است که در آن p عددی اول و کوچک تر از n است. طبق قضیه دوم مرتن $\sum_{p}\frac{1}{p}$ از مرتبه زمانی $O(log log n)$ است پس زمان اجرای این الگوریتم از مرتبه $O(n log log n)$ است.

ایده غربال کاربرد‌های دیگری نیز دارد. برای مثال کد زیر تعداد مقسوم‌الیه‌های هر عدد کوچک‌تر از n را محاسبه می‌کند.

sieve.py

def sieve(n):
    d = [0] * n
    for i in range(1, n):
        for j in range(i, n, i):
            d[j] += 1
    return d

پیچیدگی این کد اما دیگر برابر $O(n log log n)$ نیست. زمان اجرا برابر $n\sum_{1}^{n}\frac{1}{n}$ است و چون $\sum_{1}^{n}\frac{1}{n}$ از $O(log n)$ است زمان اجرای کد بالا از مرتبه $O(n log n)$ است.