Asal Sayılar

Asal sayılar, sadece kendisine ve 1’e bölünebilen, 1’den büyük olan tamsayılardır. Bu sayıları önümüze kâğıt kalem alarak bulabiliriz. Ama sayılar büyüdükçe zorlandığımızı göreceğiz. Çünkü belirli bir kuralları yoktur veya başka bir deyişle şu ana kadar bulunamamıştır. Ünlü matematikçi Fermat asal sayılar üzerinde çalışma yapmıştır. Ancak bulduğu formül tüm asal sayıları kapsamamaktadır. Asal sayıları bulurken bilgisayarı kullanmak işimizi oldukça kolaylaştıracaktır. Bu blog yazımda bir sayının asal olup olmadığını söyleyen algoritmayı, kaçıncı asal sayı isteniyorsa onu veren algoritmayı ve bu algoritmaları kullandığım bir program paylaşacağım. Sayının asal olup olmadığını söyleyen algoritma:

        bool asalMi(int sayi)  // parametre olarak aldığı sayı asalsa true değilse false döndürür

        {

            for (int i = 2; i < sayi/2+1; i++)

            {

                if (sayi % i == 0)

                {

                    return false;

                }

             }

            return true;

        }

Bu algoritma parametre olarak içine aldığı sayı asal ise true, asal değilse false döndürür. Algoritma istenilen sayıyı 2 sayısında başlayarak kendisinin yarısından 1 fazla olan sayıya kadar böler. Bu bölme işlemlerini yaparken bölümden kalan 0 olduğunda sayıya asal olmadığına hükmeder ve false döndürür. Herhangi bir bölme işlemlerinden kalan 0 çıkmaz ise o sayı asal sayıdır ve true döndürür. n. sıradaki asal sayıyı bulmak için algoritma:

        int kacinciAsalSayi(int kacinci) // parametre olarak kaçıncı asal sayı isteniyorsa o sayı gönderilir

        {

            int i = 2, kac=0; // 'kac' değişkeni bulunan asal sayısının kaçıncı asal sayı olduğunu tutacak

            for (;;)

            {

                if (asalMi(i))

                {

                    kac++; // i sayısı asal ise 'kac' değişkenini 1 artır

                }

                if (kac == kacinci)

                {

                    return i; // istenilen sıradaki asal sayıya ulaşınca döndür

                }

                i++;

            }

        }

Bu algoritma sayesinde kaçıncı sıradaki asal sayıyı bulmak isterseniz parametre olarak göndererek bulabilirsiniz. Bu algoritma 2 sayısından başlar, sayının asal olup olmadığını kontrol eder, asal ise kac değişkenini 1 artırır. kac değişkeni ile parametre olarak gönderilen kacinci değişkeni eşit olduğunda istenilen sıradaki asal sayıyı döndürür.

Programın kodlarına ulaşmak için: https://github.com/huseyinerbayat/asal-sayilar .exe olarak indirmek için:https://yadi.sk/d/VHEGYAa6jFvAy  

--Ekleme—(23.09.2015) (Yapılan yorum üzerine yapılmıştır.)

Asal sayıların daha hızlı bulunması için asalMi() fonksiyonu yerine aşağıdaki algoritmayı kullanabilirsiniz.

bool asalMi2(int sayi)  // parametre olarak aldığı sayı asalsa true değilse false döndürür

        {

            if (sayi == 2)

            {

                return true;

            }

            for (int i = 2; i < Math.Sqrt(sayi)+1; i++)

            {

                if (sayi % i == 0)

                {

                    return false;

                }

            }

            return true;

        }

Bu algoritmanın asalMi() fonksiyonun içindeki asal sayı algoritmasından farkı, sayının asal olup olmadığına karar vermek için sayısının yarısının 1 fazlasına kadar değil, sayının karekökünden 1 fazlasına kadar bölerek kontrol etmesidir. Bu yöntemin daha doğru ve hızlı olduğu açıktır. asalMi() fonksiyonunun yerine asalMi2() fonksiyonun kullanılmasını tavsiye ederim. .exe olarak indirmek için: https://yadi.sk/d/J89UGN5gjGErw Önceki ile sonraki arasındaki farkı görmek için paylaştığım iki farklı programı indirerek test edebilirsiniz. --Ekleme—(04.10.2015) Yeni bir asal sayı bulma algoritması paylaşıyorum. Bunun öncekilerden farkı asal sayıyı bulurken belli bir yere kadar olan ardışık sayıları bölerek değil, o sayıya kadar olan asal sayılara bölerek daha hızlı bir şekilde asal olup olmadığı sonucuna ulaşmasıdır.

        List<int> asalSayilar = new List<int>();

        bool asalMi3(int sayi)  // parametre olarak aldığı sayı asalsa true değilse false döndürür

        {

            if (sayi == 2)

            {

                asalSayilar.Add(sayi);

                return true;

            }

            for (int i = 0; asalSayilar[i] < Math.Sqrt(sayi) + 1; i++)

            {

                if (sayi % asalSayilar[i] == 0)

                {

                    return false;

                }

                if (i == asalSayilar.Count-1) {

                    break;

                }

            }

            asalSayilar.Add(sayi);

            return true;

        }

Burada öncelikle asalSayilar adında bir dinamik dizi oluşturuyoruz. N. sıradaki asal sayıyı bulurken 2’den başlıyor. Asal olup olmadığına bakıyor. Asal ise bu diziye ekliyor. Her zaman bir sonraki sayının asal olup olmadığını kontrol ederken bu dizideki sayılara bölüyor. Çünkü bir sayının asal olduğuna karar vermek için sadece kendinden küçük asal sayılara bölünmesi yeterlidir. Bu koşula bir de ikinci paylaştığım algoritmadaki sayının asal olup olmadığına bakmak için karekökünden 1 fazla olan sayılara kadar bölerek kontrol etmek yeterlidir koşuluyla bu koşulu birleştirdiğimizde daha hızlı bir algoritma ortaya çıkacaktır. Öncekiler ile sonraki arasındaki farkı görmek için paylaştığım iki farklı programı indirerek test edebilirsiniz: https://yadi.sk/d/ooTgnCvEjW8o3