Sonuçları anlamak
Aşağıdaki tablo, örnek girdiler için üç çıktıyı gösterir.
| Girdi | Asal mı? | Çarpanlara ayırma | Sonraki asal |
|---|---|---|---|
| 97 | Evet | 97 | 101 |
| 84 | Hayır | 2 x 2 x 3 x 7 | 89 |
| 100 | Hayır | 2 x 2 x 5 x 5 | 101 |
| 2 | Evet (tek çift asal sayı) | 2 | 3 |
| 1 | Hayır (ne asal ne bileşik) | - | 2 |
- 1 sayısı asal değildir: asal sayıların tam olarak iki farklı bölene sahip olması gerekir, 1'in ise yalnızca bir böleni vardır. 1'i hariç tutmak, asal çarpanlara ayırmanın benzersizliğini korur.
- Deneme bölmesi kesindir ancak çok büyük girdiler için yavaşlar; bu hesaplayıcı 10^12'ye kadar sayıları kabul eder, burada arama bir milyona kadar bölenleri test eder.
- Sonraki asal araması bu aralıkta hızla sonuçlanır: Bertrand'ın postülasına göre, n ve 2n arasında her zaman bir asal sayı vardır.
Asal sayı nedir?
Bir asal sayı, tam olarak iki pozitif bölene sahip olan, 1'den büyük bir doğal sayıdır: 1 ve kendisi. İlk asal sayılar 2, 3, 5, 7, 11, 13, 17, 19, 23 ve 29'dur. 2 sayısı tek çift asal sayıdır, çünkü diğer tüm çift sayılar 2'ye bölünebilir. 1'den büyük ve asal olmayan sayılara bileşik sayı denir; 1 sayısı, tanım gereği ne asal ne de bileşiktir.
Aritmetiğin temel teoremi, 1'den büyük her tam sayının, çarpanların sırası dışında, tam olarak bir şekilde asal sayıların çarpımı olarak yazılabileceğini belirtir. Bu benzersiz asal çarpanlara ayırma, asal sayıların tam sayıların yapı taşları olarak adlandırılmasının nedenidir: 84 = 2^2 x 3 x 7 ve başka hiçbir asal sayı kombinasyonu çarpıldığında 84 vermez.
Asal sayılar sonsuz sayıdadır — MÖ 300 civarında Öklid tarafından kanıtlanmış bir sonuç — ve sayılar büyüdükçe, herhangi bir basit örüntü olmaksızın, daha seyrek hale gelirler. Büyük asal sayılar, iki çok büyük asal sayının çarpımını çarpanlarına ayırmanın pratik zorluğuna dayanan modern açık anahtarlı kriptografinin (RSA gibi) temelini oluşturur.
Bu asal sayı hesaplama aracı nasıl kullanılır
- En az 1 olan bir tam sayı n girin. Ondalık sayılar en yakın tam sayıya yuvarlanarak aşağı indirilir.
- Asallık sonucunu okuyun: bir onay işareti sayının asal olduğu, bir çarpı işareti ise bileşik olduğu (veya hiçbiri olmayan 1 olduğu) anlamına gelir.
- Asal çarpanlara ayırmayı okuyun — sayınıza eşit olan asal sayıların benzersiz çarpımı. Asal bir girdi için, çarpanlara ayırma sayının kendisidir.
- Sonraki asal sayıyı okuyun, sayınızdan kesinlikle büyük olan en küçük asal sayı.
Asallık nasıl test edilir: deneme bölmesi
Bir n sayısı, ancak ve ancak 1'den büyük ve n'nin karekökünden büyük olmayan bir bölene sahipse bileşiktir. Bunun nedeni bölenlerin eşleşmesidir: eğer n = a x b ve a <= b ise, o zaman a <= sqrt(n)'dir. Bu nedenle deneme bölmesi, yalnızca sqrt(n)'ye kadar aday bölenleri test etmesi gerekir — 2 kontrol edildikten sonra, yalnızca tek aday sayılar gereklidir.
Çözülmüş örnek (asal): n = 97. 97'nin karekökü yaklaşık 9,85'tir, dolayısıyla 2, 3, 5, 7 ve 9'u test etmek yeterlidir. 97 tektir; 9 + 7 = 16, 3'e bölünmez; 0 veya 5 ile bitmez; 97 / 7 = 13,857...; ve 97 / 9 tam sayı değildir. Hiçbir bölen yoktur, dolayısıyla 97 asaldır.
Çözülmüş örnek (çarpanlara ayırma): n = 84. Asal sayıları en küçükten başlayarak bölerek çıkarın: 84 / 2 = 42, 42 / 2 = 21, 21 / 3 = 7 ve 7 asaldır. Yani 84 = 2 x 2 x 3 x 7 = 2^2 x 3 x 7. 84'ten sonraki asal sayı 89'dur (85 = 5 x 17, 86 = 2 x 43, 87 = 3 x 29, 88 = 2^3 x 11).
Sık yapılan hatalar
- 1'i asal sayı olarak saymak — tanım gereği bir asalın tam olarak iki farklı böleni vardır, 1'in ise yalnızca bir tanesi vardır.
- Tüm asal sayıların tek olduğunu varsaymak: 2 asaldır ve tek çift asal sayıdır.
- sqrt(n)'de durmak yerine bölenleri n'ye kadar test etmek — herhangi bir bileşik sayının, karekökünde veya altında bir çarpanı vardır.
- Tüm tek sayıların asal olduğuna inanmak: 9 = 3 x 3, 15 = 3 x 5 ve 21 = 3 x 7 tek bileşik sayılardır.
- Asal çarpanlara ayırmayı herhangi bir çarpanlara ayırmayla karıştırmak: 84 = 4 x 21 bir çarpanlara ayırmadır, ancak asal çarpanlara ayırma 2 x 2 x 3 x 7'dir.
Sıkça Sorulan Sorular
Bir sayının asal olup olmadığını nasıl kontrol ederim?
2'den sayının kareköküne kadar herhangi bir tam sayının onu tam olarak bölüp bölmediğini test edin. Hiçbiri bölmüyorsa, sayı asaldır. 97 için karekök yaklaşık 9,85'tir ve 2, 3, 5, 7 veya 9'dan hiçbiri 97'yi bölmez, dolayısıyla 97 asaldır. Bölen çiftleri, herhangi bir bileşik sayının karekökünde veya altında bir çarpanı olmasını garanti eder.
Neden 1 bir asal sayı değildir?
Bir asal, tam olarak iki farklı pozitif bölene, 1 ve kendisine sahip olarak tanımlanır; 1 sayısının ise yalnızca bir böleni vardır. Bu tanım, aynı zamanda aritmetiğin temel teoremini de korur: eğer 1 asal olsaydı, çarpanlara ayırmalar artık benzersiz olmazdı (6 = 2 x 3 = 1 x 2 x 3 = 1 x 1 x 2 x 3 ve böyle devam eder).
Asal çarpanlara ayırma nedir?
Bu, bir sayının asal sayıların çarpımı olarak ifadesidir ve aritmetiğin temel teoremi, sıralama dışında bunun benzersiz olduğunu garanti eder. Örneğin, 84 = 2 x 2 x 3 x 7. Bulmak için, kalan bölüm 1 veya asal olana kadar tam olarak bölen en küçük asal sayıyı tekrar tekrar bölerek çıkarın.
2 bir asal sayı mıdır?
Evet — 2 asaldır çünkü tek bölenleri 1 ve 2'dir ve tek çift asal sayıdır. Diğer tüm çift sayılar 2'ye bölünebilir ve bu nedenle bileşiktir. Bu yüzden asallık testleri 2'yi ayrı olarak ele alır ve ardından yalnızca tek aday sayıları kontrol eder.
Kaç tane asal sayı vardır?
Sonsuz sayıda, MÖ 300 civarında Öklid'in kanıtladığı gibi: herhangi bir sonlu asal sayı listesi verildiğinde, hepsinin çarpılıp 1 eklenmesiyle oluşan sayı bunların hiçbiri tarafından bölünmez, dolayısıyla listede eksik olan bir asal sayı vardır. Asal sayılar, sayılar büyüdükçe seyrekleşir — asal sayı teoremine göre, n'ye yakın asal sayıların yoğunluğu kabaca 1 / ln(n)'dir — ancak asla durmazlar.
Asal sayılar kriptografide neden önemlidir?
RSA gibi açık anahtarlı sistemler bir asimetriye dayanır: iki büyük asal sayıyı çarpmak kolaydır, ancak pratikte kullanılan boyutlarda (yüzlerce basamak) çarpımlarından asal sayıları geri elde etmek hesaplama açısından zordur. Güvenlik anahtarları bu tür çarpımlardan oluşturulur, bu nedenle asal sayı üretimi ve asallık testi temel kriptografik işlemlerdir.
Kaynaklar
- Weisstein, Eric W. "Prime Number" and "Fundamental Theorem of Arithmetic." MathWorld — A Wolfram Web Resource. mathworld.wolfram.com.
- Hardy GH, Wright EM. An Introduction to the Theory of Numbers. Oxford University Press (primes, unique factorization, Bertrand's postulate).
- Euclid. Elements, Book IX, Proposition 20 (infinitude of primes).