Asal Çarpanlar

Bilgisayar dünyasının, üstünde en çok tartışılan konularından biri de, asal sayıların bilgisayarlar tarafından nasıl en hızlı ve kısa biçimde (bir başka deyişle en rasyonel biçimde) bulunabileceği olmuştur. Biz de bunun BASIC ve makine dilindeki çeşitli çözümlerini sunuyoruz. Bunu yaparken özellikle bazı öğrenci arkadaşlara yardımcı olmayı umuyoruz.

Bilindiği gibi, asal sayılar sadece kendilerine ve 1'e bölünebilen sayılardır. 2'den başlayarak sonsuza dek giderler (2,3,5,7,11,13,17...). Matematiksel olarak, her asal sayıdan sonra en az bir asal sayı daha olduğu ispatlanmıştır.

Elimize kağıt kalemi alıp asal sayıları bulurken başlangıçla zorlanmayabiliriz, ama şu sayıların da birer asal sayı olduklarını hesaplayabilir miydiniz?

1201, 9721, 379721, 66369101

Bir diğer konu da, verilen bir sayıyı asıl çarpanlarına ayırmaktır. Örneğin 1470=2*3*5*7↑2. Ancak şunları elle hesaplayabilir miydiniz?..

1197=3↑2*7*19

1234567=127*9721

9876543210=2*3↑2*5*17↑2*379721

İşte, bu tip problemlerin çözümü günümüzde bilgisayarlara bırakılmıştır. Biz de COMMODORE 64'ümüzü bu işte kullanabiliriz.

Önce belli bir sayıya kadar olan tüm asal sayıların listesini elde etmek problemiyle uğraşalım. Bunun için, günümüzde de hâlâ geçerliliğini koruyan en basit yöntemi MÖ 3. yüzyılda yaşamış olan Eratosthenes önermiştir. Yöntem çok basittir: Önce tüm sayıların bir listesini yaparız, sonra başlarız bunları yazmaya. Ama her sayıyı yazdıktan sonra, o sayının tamkatlarını listemizden sileriz. Böylece yazacağımız sayılar, aradığımız asal sayılar olacaktır.

İşte bu yöntemi, ASAL SAYILAR programı ile gerçekleştirdik.

10: Üst sınır kullanıcıdan isteniyor. Ancak bu sayının 19000'den küçük olması gerekmekte, yoksa bilgisayarın hafızası yetmemektedir.

20: Programın çalışmasını hızlandırmak için, 1 ve 0 değerleri değişkenlere yerleştiriliyor. Sonra da tüm sayıların listesinin yerini tutacak matris oluşturuluyor. Bu matrisin herhangi bir elemanının 1 olması, o elemanın karşılık geldiği ve indis tarafından gösterilen

sayının, asal bir sayı olduğu anlamına gelmektedir.

30: Üst sınıra kadar olan tüm sayıları kapsayan döngü başlatılıyor. Eğer sırası gelen sayı, genel listeden silinmişse bir sonraki sayının kontrolü için 60 numaralı satıra geçiliyor.

40: Bulduğumuz sayı asal bir sayı olduğuna göre, ekrana yazabiliriz. Bundan sonra da, o sayının katlarını listemizden silmek zorundayız.

50: İşte silme işlemi de burada gerçekleşiyor.

Bu program, küçük sayılar için yeteri kadar hızlı olsa bile, büyük sayılar için oldukça yavaş kalmaktadır. İsterseniz, 19000'i bir deneyin...

Bir sonraki adımımız, bir sayıyı asal çarpanlarına ayırmak olacak. Önce BASIC ile nasıl yapabileceğimizi görelim. ASAL ÇARPANLAR, B programı bu işlemi yapar.

5: Gene 0 ve 1'i değişkenlere yerleştiriyoruz.

10: Sayıyı okuyup, listemizi hazırlıyoruz.

11-16: Listemizde sadece asal sayılar kalacak şekilde, bir önceki programın yönetimini kullanıyoruz.

20: Artık sayımızı sırasıyla bütün asal sayılara bölecek olan döngüye girebiliriz. Eğer sırası gelen sayı asal bir sayı değilse, bir sonraki sayıya geçilecektir.

25-40: Esas sayımızın, o anki asal sayıya bölünüp bölünmediği ve bölünüyorsa, kaç kez bölünebildiği burada bulunuyor.

80-90: Demin bulunan sonuca göre, çarpım ve üs alma işlemleri yazılıyor.

100: Bir sonraki sayıya geçiliyor ve tüm sayılar bitince, en sonda yazılmış olan çarpı işareti siliniyor.

Yukarıda açıklamalarını yaptığımız her iki program da bazı ortak dezavantajlara sahipler.

Öncelikle her ikisi de çok yavaş. Bunda en önemli etken, BASIC'de yazılmış olmaları.

Bir diğer olumsuz yan da, çok fazla hafıza gerektirmeleri. Çünkü her defasında tüm sayıları içeren bir liste hazırlamak ve her sayı için bu listeyi sonuna kadar yeniden taramak gerekiyor. Tabii, bunun kaçınılmaz sonucu yavaşlık ve hafıza kaybı.

Ayrıca BASIC, sadece belli bir limite kadar olan tamsayıları kabul eder; bundan sonra gelen sayılar ondalık sayı olarak saklanır. Bu hem hesaplamaları güçleştirir, hem de hesaplamalardaki doğruluk oranını düşürür.

Bir diğer yöntem, asal sayıları bir ön liste hazırlamadan bulmaktır. Bu durumda bir sayının asal sayı olup olmadığını, o sayı için baştan araştırmak zorundayız. Bu işlemi de ASAL SAYILAR 2 adlı programımızda gösterdik.

10: Sayının okunması.

20: Verilen sayıya kadar olan tüm sayıları tarayan döngü başlıyor. Eğer FL, 60 numaralı satıra kadar sıfır olarak kalırsa, o sayı asal bir sayı demektir.

30-50: O anki sayıyı, 2 ile kendi karekökünün bir fazlası arasındaki sayılara sırayla bölerek, bu sayılardan tam olarak bölünüp bölünmediğini öğreniyoruz. Eğer böyle bir bölünme varsa ve bu bölünmeyi yapan kendisine eşit bir sayı değilse (bu şart küçük sayılar için konmak zorunda), bu durumda o sayı bir asal sayı değildir. Döngüyü terk etmek için gereken işlemleri yapıp, FL'yi 1 durumuna getiriyoruz. Taramayı SQR(I)+1'e kadar yapmamızın nedeni şöyle açıklanabilir: Örneğin, 234 sayısı 16'ya kadar olan sayılardan birine tam olarak bölünmemişse, 16'dan sonraki sayılara da bölünemeyecek demektir. Eğer bölünebilseydi, bölüm 16'dan küçük olmak zorunda kalırdı ki, bu da 16'dan önceki sayılara o ana kadar bölünememiş olmasıyla çelişirdi.

60-70: Bulunan sayı asal ise ekrana yazılıyor ve bir sonraki sayıya geçiliyor.

Bu yöntemin yararı, üst sınır olarak hafızaya bağımlı olmamasıdır. Dolayısıyla bir sayıyı asal çarpanlarına ayırırken kullanılması gereken metod budur. Ancak gene de çok yavaş kalacaktır. Bu yöntemin ilk programdan farkı, ekrana yazılan son sayı büyüdükçe programın yavaşlamasıdır. İlk programda ise, üst sınıra yaklaştıkça program hızlanmaktaydı.

Bize son olarak, makine dilinde yazılmış oldukça hızlı ama ne yazık ki yaptığı matematiksel işlemler nedeniyle oldukça da uzun bir program daha veriyoruz. Bu program, en son tartıştığımız asal sayı belirleme yöntemiyle asal çarpanlara ayırma programını birleştirmektedir. 19 basamağa kadar olan tüm sayıların asal çarpanlarını kısa sürede bulabilmektedir. Basamak sayısı arttıkça işlem süresi de artmaktadır, ancak gene de BASIC'de günler alabilecek işlemler bu programda 5-10 dakika içinde (çok ender olarak bu zaman sınırıyla karşılaşabilirsiniz) yapılmaktadır.

Programı MDE ile yazıp, LİST ettiğinizde ufak bir BASIC başlangıç göreceksiniz. Lütfen bu kısım üstünde hiçbir değişiklik yapmayın, yoksa program işlemez. İstediğiniz zaman programı RUN/STOP ile durdurabilir. RUN ile de başlatabilirsiniz.

Başta da söylediğimiz gibi, matematikçilerin en çok hoşlandıkları alanlardan biri olan bu konu ve en sonda sunduğumuz program, umarız birçok öğrenci arkadaşımıza yeterli olur.