Asal Sayı Algoritmaları

Naive: O(√n)

def is_prime(n):
    if n < 2: return False
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

Neden √n? Eğer n = a*b ise, en az bir çarpan √n'den küçük olmalı.

Optimizasyon: 6k ± 1

Tüm asallar 6k±1 formundadır (2 ve 3 hariç):

def is_prime(n):
    if n < 2: return False
    if n < 4: return True
    if n % 2 == 0 or n % 3 == 0: return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

Eratosthenes Eleği: O(n log log n)

Çok sayıda asal kontrolü için:

def sieve(n):
    primes = [True] * (n + 1)
    primes[0] = primes[1] = False
    for i in range(2, int(n**0.5) + 1):
        if primes[i]:
            for j in range(i * i, n + 1, i):
                primes[j] = False
    return [i for i, p in enumerate(primes) if p]

Performans Karşılaştırması

| n | Naive | 6k±1 | Sieve (10 tekrar için) |

|---|-------|------|------------------------|

| 10⁶ | 1ms | 0.5ms | 50ms (10× kontrol için) |

| 10⁹ | 30ms | 15ms | 800ms |

Kullanım Alanları