Yükleniyor // RUNTIME_INITIALIZINGAlgoritma ve bileşen ağacı hazırlanıyor...
Bir sayının asal olup olmadığını sınayan temel ve optimize edilmiş bölünebilirlik testidir.
Primality Test, bir tam sayının asal olup olmadığını belirlemek için kullanılan matematiksel testtir. DSA notlarında en temel asallık testinin 2'den başlayarak n-1'e kadar bölme denemesi yaptığı, ancak asıl kontrolün sqrt(n) sınırına kadar yapılmasının yeterli olduğu açıklanır.
Daha gelişmiş yöntemler büyük sayılarda Miller-Rabin gibi olasılıksal testleri kullansa da, deterministik deneme bölmesi (trial division) yaklaşımı küçük ve orta büyüklükteki sayılar için son derece hızlı ve güvenilirdir.
Aşağıdaki uygulamalar PDF kaynaklarındaki pseudo kod akışını modern veri yapılarıyla ifade eder. Kenar durumları görünür bırakıldığı için örnekler doğrudan test edilebilir.
1function isPrime(n: number): boolean {2 if (n <= 1) return false;3 if (n <= 3) return true;4 if (n % 2 === 0 || n % 3 === 0) return false;5 for (let i = 5; i * i <= n; i += 6) {6 if (n % i === 0 || n % (i + 2) === 0) return false;7 }8 return true;9}Asallığını test etmek istediğiniz sayıyı girin. Örnek: 97
Asallığını test etmek istediğiniz sayıyı girin. Örnek: 97
En İyi Durum: O(1)
Ortalama Durum: O(sqrt(n))
En Kötü Durum: O(sqrt(n))
O(1) - Giriş boyutu ne olursa olsun, algoritma her zaman aynı sürede çalışır.
Primality Test (Asallık Testi) Algoritması ile benzer veya alternatif olarak değerlendirilebilecek diğer başlıklar: