Project Euler 3: En Büyük Asal Çarpan

Soru: 13195 sayısının asal çarpanları 5, 7, 13 ve 29'dur. 600851475143 sayının en büyük asal çarpanı nedir?

Project Euler'in üçüncü sorusunda karşımıza yine bir algoritma klasiği çıkıyor: Asal sayılar.

Asal sayıları elde edebileceğimiz bir sürü algoritma mevcut. Bunları incelemenizi şiddetle tavsiye ediyorum. Bir sayının asal sayı olup olmadığını denetlemenin en kaba yolu o sayıyı kendisine kadar olan sayma sayılarına bölmektir. Bu sayı bir ve kendisi hariç başka bir sayıya bölünmüyorsa asal bir sayıdır. Fakat bu yöntem fazlasıyla gereksiz işlem kalabalığına sahiptir. Örneğin hiçbir asal sayı çift değildir, çünkü çift her sayı ikinin bir katıdır. Bu yüzden her seferinde çift sayıları kontrol etmek anlamsızdır. (Takdir edersiniz ki bu iki kat fazla sayının kontrol edilmesi demek) Bu soruda biz de tam olarak bu mantıktan ilerleyen bir algoritmayı ele alacağız.

Eratosthenes'in Eleği Algoritması

Sieve_of_Eratosthenes_animation

Bu algoritma 'den başlayarak eleme yöntemiyle asal sayıların belirlenmesini sağlar. Öncelikle ilk sayı olan asal olarak yazılır ve eldeki listeden 'nin katları silinir. Sonra sıradaki sayı olan 'e geçilir ve 'ün katları silinir. Sıradaki sayı değildir, çünkü 'nin katı olduğundan elenmiştir. Dolayısıyla sıradaki sayı 'tir, asal olarak yazılır ve katları silinir. İşlem bu şekilde devam eder. Geriye kalan sayılar asal sayılardır.

Denetlemeyi sayının kareköküne kadar olan sayılara kadar yapmak yeterlidir. Örneğin sayısının asal olup olmadığını denetlemek için 'a kadar olan sayılara bakmak yeterlidir. (Bu yöntemin bizi ne kadar işlem kalabalığından kurtardığına dikkat edin.)

Eğer sayıları bir dizide kabul eder ve dizinin asal olmayan elemanlarına yanlış değerini atarsak, dizinin doğru olan elemanlarının numarası bize asal sayıları verir. Böylece kodumuz aşağıdaki şekilde olur.

static ArrayList SieveOfEratosthenes(int AsalLimit)
{
    BitArray bitArray = new BitArray(AsalLimit, true);

    int SonAsal = 1;
    int SonAsalKok = 1;

    while (SonAsalKok <= AsalLimit)
    {
        SonAsal++;

        while (!(bool)bitArray[SonAsal])
            SonAsal++;

        SonAsalKok = SonAsal * SonAsal;

        for (int i = SonAsalKok; i < AsalLimit; i += SonAsal)
            if (i > 0)
                bitArray[i] = false;
    }

    ArrayList AsalSayılar = new ArrayList();

    for (int i = 2; i < AsalLimit; i++)
        if (bitArray[i])
            AsalSayılar.Add(i);

    return AsalSayılar;
}

Şimdi yapmamız gereken işlem, bize verilen sayı olan 'ün karaköküne kadar olan asal sayıları Eratosthenes'in Eleği yöntemini kullanarak oluşturmak. Ardından sayımızı bu asal sayılara bölerek, hangisinin en büyük asal çarpan olacağını bulabiliriz.

int AsalLimit = (int)Math.Sqrt(600851475143);
ArrayList Asallar = SieveOfEratosthenes(AsalLimit);

    foreach (int Asal in Asallar)
    {
        if (600851475143 % Asal == 0)
        {
            Console.WriteLine(Asal);
        }
    }

Sonuç: 71, 839, 1471, 6857 olarak bulunur.

Ögetay Kayalı

Ögetay Kayalı

Astronom. Özel ilgi alanı teorik kozmoloji, özellikle Einstein'ın görelilik kuramının modifiye edilmesi (modified gravity) üzerine uğraşıyor. Bunların yanında ender bulduğu zaman aralıklarında kafasına esince programlama, 3B modelleme, makineler, tasarım, fotoğrafçılık, resim ve satranç ile de ilgileniyor.

Ögetay Kayalı 120 makale yazdıÖgetay Kayalı tarafından yazılan tüm makaleleri gör