Asal Sayı Denetleyicisi (çarpanlara ayırma ile)

Asal sayı nedir

Asal sayı, 1 ve kendisinden başka pozitif böleni olmayan 1'den büyük doğal bir sayıdır. İlk birkaç asal sayı: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37. Bunlar tam sayı aritmetiğinin 'atomları'dır — 2'ye eşit veya büyük her tam sayı benzersiz biçimde asal sayıların çarpımı olarak yazılabilir (Aritmetiğin Temel Teoremi).

1 uzlaşı gereği asal değildir. 0 ve negatif sayılar asal değildir. 2 tek çift asal sayıdır — diğer tüm çift sayılar 2 ile bölünebilir ve dolayısıyla bileşiktir.

Test nasıl çalışır

Deneme bölmesi kullanıyoruz: √n'e kadar 2, ardından 3, ardından 5, 7, 11... ile bölünebilirliği kontrol edin. Hiçbiri temiz bölmüyorsa n asaldır. 3'ten büyük tüm asal sayılar 6k+1 veya 6k-1 biçiminde olduğundan yalnızca bu formattaki adayları kontrol eden 6k±1 optimizasyonunu kullanıyoruz; bu test sayısını 2/3 oranında azaltır.

Deneme bölmesi ~10^15'e kadar n için hızlıdır (saniyenin altında). Bunun ötesinde Miller-Rabin (olasılıksal) veya AKS (belirleyici) gibi gelişmiş testler gereklidir. Aşırı girdilerde tarayıcının donmasını önlemek için 10^18'de sınırlandırıyoruz.

Asal sayılar neden önemlidir

Kriptografi: RSA şifrelemesi çarpanları büyük oluşturmak güç olan bir sayı üretmek için yaklaşık 1000 basamaklı iki asal sayıyı çarpar. Güvenlik, büyük sayıları çarpanlara ayırmanın güçlüğüne dayanır — binlerce yıldır incelenen bir zorluk.

Matematik eğitimi: asal çarpanlara ayırma temeldir. GCD, LCM, modüler aritmetik, kesirler ve sayı teorisi gibi kavramlar asal çarpan yapısı üzerine inşa edilir.

Bilgisayar bilimi: hash tablo boyutları, rastgele sayı üreteçleri ve birçok algoritma asal sayıların kendine özgü bölünebilirlik özelliklerini kullanır.