Bilindiği gibi asal sayılar 1 ve kendinden başka böleni olmayan sayılardır ve binlerce yıldır insanoğlunun merakını celbetmiştir. Bir çok düşünür ve matematikçi asal sayıları tespit edecek bir formül bulma çabası içine girmiş ve fakat bu çabalar hüsranla sonuçlanmıştır. Çünkü asal sayıları tespit etmenin herhangi bir formülü maalesef yoktur. Bazı yaklaşım metotları belli sayılara kadar doğru sonuç verse de maalesef tüm sayılar için genel bir yaklaşım ortaya konulamamıştır.
Asal bir a için 2a – 1 biçiminde yazılan sayılara Mersenne sayıları denir. Peki, a asalsa, Ma = 2a – 1 olarak tanımlanan sayı da asal mıdır?
İlk Mersenne sayılarına bakalım:
M2 = 3
M3 = 7
M5 = 31
M7 = 127
Bu sayıların herbiri asal. Ama bundan sonraki ilk Mersenne sayısı, yani M11, asal değil: M11 = 23 x 89.
Hangi asallar için Ma asaldır? Yanıt bilinmiyor.
Fermat, Fn =(2²)^n +1 biçiminde yazılan bütün sayıların asal olduklarını sanıyordu. Bu yüzden bu sayılara Fermat sayıları denir. Gerçekten de ilk beş Fermat sayısı,
Fo = 3
F1 = 5
F2 = 17
F3 = 257
F4 = 65537 asaldır.
Fermat, bütün Fermat sayılarının asal olduklarını kanıtlamaya uğraştı ama başaramadı. Başarısızlığının nedeni vardı: Sanısı doğru değildi. F5 asal değildir. F5 on basamaklı bir sayı olduğundan asallığını kanıtlamak kolay değildi. Euler (1707-1783), F5’in 641’e bölündüğünü gösterdi:
F5 = 641 x 6700417.
Peki, anlaşılan o ki asal sayıları tespit etmek sanıldığının aksine hiçte kolay değil. Ancak bir sayının asal olup olmadığını nasıl anlarız sorusunun cevabını bilgisayar yardımı ile çok hızlı bir şekilde tespit edebiliriz. Nasıl mı?
Sayımıza n diyelim. n’yi n’den küçük sayılara bölmeye çalışalım. Eğer n’den küçük, 1’den büyük bir sayı n’yi tam bölüyorsa, n, tanımı gereği, asal olamaz. Öyle bir sayı bulamazsak, n asaldır deriz.
Ne var ki bu yöntemle büyük sayıların asallığına karar vermek çok zaman alır. Bu yöntem ve çeşitlemeleri dışında bir sayının asallığına karar verebilecek genel bir yöntem de bilinmemektedir. Örneğin, şu çeşitleme düşünülebilir: n’yi n’den küçük her sayıya böleceğimize, n’yi √n’den küçük sayılara bölmeye çalışabiliriz. Çünkü n = ab ve a ≥√n ise, b≤√n’dir. Dolayısıyla n asal değilse, √n’den küçük bir sayıya bölünür. Böylece yapmamız gereken bölme sayısı azalır.
Peki, bunu yapacak bir algoritma yazalım. Bunun için Flowgorithm programı ile bir flowchart oluşturalım. Aşağıda oluşturulmuş bir flowchart bulunmaktadır. Bu yöntemle çok hızlı bir şekilde herhangi bir sayının asal olup olmadığını bulmak mümkün.
Flowchart’ı buradan indirebilirsiniz.
Daha hızlı bir algoritma olabilir mi sizce?