Sprawdzanie liczby pierwszej — Zadanie rekrutacyjne #5

Czego szuka rekruter: optymalizacja algorytmu, rozumienie złożoności, edge cases
Poziom: Junior / Mid

Zadanie

Napisz funkcję IsPrime(int n), która zwraca true jeśli n jest liczbą pierwszą, false w przeciwnym przypadku.

Liczba pierwsza to liczba naturalna większa od 1, podzielna tylko przez 1 i przez siebie.

Czego szuka rekruter

To zadanie o optymalizacji algorytmu. Naiwne rozwiązanie O(n) jest poprawne ale nieoptymalne. Rekruter sprawdza czy kandydat:

• Zna optymalizację do O(√n) i potrafi ją wytłumaczyć
• Pamięta o edge cases: n ≤ 1, n = 2, n = 3
• Zna drobną optymalizację z liczbami parzystymi

Edge cases

❌ Naiwne rozwiązanie — O(n)

static bool IsPrimeNaive(int n)
{
    if (n <= 1) return false;
    for (int i = 2; i < n; i++)
        if (n % i == 0) return false;
    return true;
}

Dla n = 1_000_000_007 sprawdza miliard dzielników. Wolne.

✅ Optymalne rozwiązanie — O(√n)

static bool IsPrime(int n)
{
    if (n <= 1) return false;
    if (n <= 3) return true;              // 2 i 3 są pierwsze
    if (n % 2 == 0 || n % 3 == 0) return false;  // eliminuj parzyste i wielokrotności 3
    
    // Wszystkie liczby złożone mają dzielnik ≤ √n
    // Pozostałe dzielniki mają postać 6k±1
    for (int i = 5; (long)i * i <= n; i += 6)
    {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

Dlaczego √n? Jeśli n ma dzielnik d > √n, to ma też dzielnik n/d < √n. Wystarczy sprawdzić do √n.

Dlaczego 6k±1? Po eliminacji wielokrotności 2 i 3, pozostałe liczby mają postać 6k±1. Sprawdzamy tylko je, co redukuje liczbę iteracji o ~66%.

Sito Eratostenesa — gdy sprawdzasz wiele liczb

Jeśli musisz sprawdzić czy wiele liczb z zakresu [2, n] jest pierwszymi — sito jest O(n log log n) i jest zdecydowanie szybsze niż wywoływanie IsPrime dla każdej z osobna.

static bool[] SieveOfEratosthenes(int max)
{
    var isPrime = new bool[max + 1];
    Array.Fill(isPrime, true);
    isPrime[0] = isPrime[1] = false;
    
    for (int i = 2; (long)i * i <= max; i++)
    {
        if (isPrime[i])
        {
            for (int j = i * i; j <= max; j += i)
                isPrime[j] = false;
        }
    }
    return isPrime;
}

// Znajdź wszystkie liczby pierwsze ≤ 1000:
var sieve = SieveOfEratosthenes(1000);
var primes = Enumerable.Range(2, 999).Where(i => sieve[i]).ToList();

Testy jednostkowe

[Theory]
[InlineData(1,  false)]
[InlineData(2,  true)]
[InlineData(3,  true)]
[InlineData(4,  false)]
[InlineData(17, true)]
[InlineData(25, false)]  // 5×5
[InlineData(97, true)]
[InlineData(1_000_000_007, true)]
public void IsPrime_ReturnsCorrectResult(int n, bool expected)
{
    Assert.Equal(expected, IsPrime(n));
}

Co powiedzieć na rozmowie

“Optymalizacja do √n wynika z faktu, że jeśli n jest złożone, to jeden z jego dzielników jest ≤ √n. Dodatkowa optymalizacja z 6k±1 eliminuje wielokrotności 2 i 3 zanim wejdziemy w pętlę, co skraca ją o dwie trzecie. Jeśli potrzebujemy sprawdzić wiele liczb w zakresie — sito Eratostenesa jest lepsze, bo generuje wszystkie liczby pierwsze do n w O(n log log n).”

Podsumowanie