bir matematik gizemi: asal sayılar

      Geçenlerde Tubitak'ın sitesinde bilgi yarışması gördüm ve merak edip açtım. Karşıma çıkan soruları merakla incelemeye başladım haliyle. Ancak daha ilk soru kafamda onlarca soru işareti oluşturmaya yetmişti ne yazık ki :) Şöyle ki; 2.000.000'dan sonraki ilk asal sayıyı soruyordu sorunun bir kısmında ki takıldığım nokta da orası oldu. Asal sayı bildiğim düz mantıkla 1'den ve kendisinden başka herhangi bir sayıya bölünmeyen sayı olmalıydı. Hal böyle olunca bu sayı için o kadar işlem yapılamazdı. Bunun bir yöntemi, bir formülü olmalıydı ve o sırada yanımda bulunan matematikçi arkadaşa danıştım. Ancak o da tam emin olamadı bu durum konusunda. Bunun üzerine internette araştırmalar yaptım ve karşıma üzerinde çaba sarfedildiği her halinden belli olan çeşitli formüller ve algoritmalar çıktı ancak bu da iş görmez nitelikteydi. İnsan eliyle bu formülleri uygulayıp denemek oldukça zahmetli olacaktı ve ben de ufak bir hilye başvurdum; bilgisayara :)

      Tercihim c++'dan yana oldu, haliyle derleyicim de favorim olan code::blocks oldu. İlk seferinde düz mantıkla ilerledim ve sayıları kendisine kadarki olan sayılara bölmekle yetindim:

bool asalKontrolDuzMantik(int gelen)
{
    int sayi = 2;
    if(gelen<2)
        return false;
    for(; sayi < gelen; sayi ++)
        if(gelen%sayi== 0)
            return false;
    return true;
}

      Haliyle iş görmez bir fonksiyon değildi ancak hantal olduğu inkar dilemezdi zira main'de fonsiyonumu 1'den 500.000'e kadar çağırdığımda oldukça vakit alıyordu yapılan işlemin süreci. Çünkü bir asal sayıya denk geldiğinde işlem o sayıya gelene kadarki süreç zarfında sürekli bölünüyor ancak bir sonuç elde edilemiyordu. Eğer ki hızlı işlem yapmanın önemli olduğu bir proje üzerinde çalışılıyorsa bu bir sorun teşkil etmekte bizim için. Bu sorunu gidermek için asal sayıların genel mantığı üzerinde internette yaptığım araştırmalar sonucunda sis perdesi biraz daha aralandı. Şöyle ki;
      Bir sayı için; kendisinin karekökü bir dönüm noktasıdır. Eğer ki sayı asal sayı ( 53 = 53 x 1 ) veya bir asal sayının karesi değilse ( 49 = 7 x 7 ) o zaman bu sayı kareköküne kadarki gelecek olduğumuz süreç içersinde bir sayıya elbette ki bölünecektir ( 51 = 3 x 17, 12 = 2 x 2 x 3 ). Asal sayının karesi olan sayımız ( 49 ) ise kareköküne ( 7 ) bölüneceği için o sıraya gelene kadarki sayılar onun için bir anlam ifade etmeyecektir.  Karekökünden sonra gelecek olan sayılar ise karekökünden önce gelecek olan sayıların yanıması olmaktan öteye gidemeyecektir. Bu noktadan sonra ikinci kez aynı sayılarla işleme tabi tutmuş olmaktan başka birşey yapmış olmayacağız.  
      Örneğin asal olmayan aşağıdaki sayılar için;

• 132 ( 132 = 11 x 12 ) sayısının karekökü yaklaşık 11,48'dir.
• 391 ( 391 = 17 x 23 ) sayısının karekökü 19,77'dir.
• 8633 ( 8633 = 89 x 97 ) sayısının karekökü 92,91'dir.

Bu sayılar kareköklerine gelene kadarki bir sayıya muhakkak bölünecektir.
      Tamam ama bu noktada şu düşünülemez miydi; bu sayılar kendisine kadar döndürülse ne değişecekti ki? yine bölen bir sayıya denk geldiğinde bölünecek ve işlemden çıkacaktı ve karekökünün hesaplanmasının derdine düşülmeyecekti! Aslında bu sorunun yanıtı "Evet" olacaktır. Evet çünkü bu sayılar ha kendisine ha kareköküne kadarki olan sayı kez döndürülsün yine o sayıya ulaşınca işlemden çıkacaktı ANCAK; önemli olan nokta asal sayılarda yer alıyor. Asal olmayan sayılar için değişen birşey yok onlar yine bölünmeye devam edecekti ancak asal sayılar için düz mantıkla ilerlemiş olsaydık, özellikle de 2.000.003 asal sayısını düşünecek olursak, kendisine gelene kadar for döngüsüne tabi tuttuğumuz zaman bilgisayar aşırı vakit kaybettiriyor bize. Ancak kareköküne, 1414,21 sayısına, kadarki işleme bakılacak olunursa işlem fark edilir derecede hızlanıyor.

      Aşağıdaki fonksiyon incelenecek olunursa bu fonksiyonun karekök kullanılarak nasıl iyileştirildiği görülmektedir. Girilen sayı kareköküne kadar kendisine bölünmektedir.

bool asalKontrolKarekoklu(int gelen)
{
    int sayi = 2;
    if(gelen<2)
        return false;
    for(; sayi <= sqrt(gelen); sayi ++)
        if(gelen%sayi== 0)
            return false;
    return true;
}

      Ancak bu fonksiyonumuz halihazırda yine de hantaldır diyebiliriz. Tam manasıyla bir iyileştirme yapabilmek için karekök ( sqrt() ) fonksiyonunun for döngüsünün dışarısına çıkarılması lazımdır. Zira her for döngüsünde bir karekök hesaplanması yerine bir kez döngü başında hesaplanması ve bu sayının kullanılması daha mantıklı olacaktır. Yani;

bool asalKontrolIyilestirilmis(int gelen)
{
    int son,sayi = 2;
    if(gelen<2)
        return false;
    son=sqrt(gelen);
    for(; sayi <= son; sayi ++)
        if(gelen%sayi== 0)
            return false;
    return true;
}

son değişkeni bir kere karekökü hesaplayıp for döngüsüne kendisini sokmakta ve bu şekilde işleme devam etmektedir. Şimdi ise bu üç fonksiyonun işlem sürelerinin bir karşılaştırmasını göstereyim hemen:

      Örnekten de anlaşılacağı üzere kareköklü ve iyileştirilmiş fonksiyonumuz hayli fark atmış bulunmakta. İlk fonksiyon yaklaşık olarak 3 dakikalık bir süre harcadıktan sonra işlemini tamamlamaktadır. 

     Bu süreci hesaplamak için kullandığım main fonksiyonu ise;

int main(){
    clock_t bas1, bas2, bas3, son1, son2, son3;
    int k,sonuc1,sonuc2,sonuc3;
    k=sonuc1=sonuc2=sonuc3=0;

    bas1 = clock();
    for (int i=0;i<3;i++)
    {
        if(i==1)
        {
            son1 = clock();
            bas2= clock();
        }
        else if(i==2)
        {
            son2 = clock();
            bas3= clock();
        }
        for(k=0;k<500000;k++)
        {
            if(i==0)
            {
                if(asalKontrolDuzMantik(k))
                    sonuc1++;
            }
            else if(i==1)
            {
                if(asalKontrolKarekoklu(k))
                    sonuc2++;
            }
            else if(i==2)
            {
                if(asalKontrolIyilestirilmis(k))
                    sonuc3++;
            }
        }
    }
    
    son3 = clock();    
    cout<<"1. Toplam Asal Sayisi: "<<sonuc1<<" , Toplam Sure: "<<(son1-bas1)/CLOCKS_PER_SEC<<endl;
    cout<<"2. Toplam Asal Sayisi: "<<sonuc2<<" , Toplam Sure: "<<(son2-bas2)/CLOCKS_PER_SEC<<endl;
    cout<<"3. Toplam Asal Sayisi: "<<sonuc3<<" , Toplam Sure: "<<(son3-bas3)/CLOCKS_PER_SEC<<endl;
    
    getchar();
    return 0;
}

Bu arada unutmuşum Tubitak'ın sorusunu; 2.000.000'dan sonraki ilk asal sayı 2.000.003'müş. Yazmış olduğum bu küçük programcık sayesinde buldum. :) Bu blog adresini aynı soruyu araştırarak bulan arkadaşlara yardımcı olmuş da olalım o zaman :)