Project Euler 7: 10001. Asal Sayı

İlk altı asal sayı; 2, 3, 5, 7, 11, 13'tür. Altıncı asal sayı 13 olduğuna göre 10001. asal sayı kaçtır?

Aslında bu problemi daha önce çözdük. Problem 3'te, en büyük asal çarpanı bulmamızı isterken, asal sayıları bulan bir algoritma kullanmıştık. Madem çözmüştük, neden sonraki sorularda karşımıza çıktı diye düşünebilirsiniz. Fakat, programlamaya yeni başlayan biri, önceki problemde bizim kullandığımız algoritmayı muhtemelen bilmiyor olacaktır. Asal sayılar, algoritma mantığını öğretmek için harika araçlardır. Eğer kaba kuvvet (brute force) kullanarak asal sayıları bulmaya çalışırsanız, işte bu problemde başınız yanmaya başlıyor.

İstenilen basamak arttıkça, yapılması gereken işlemler katlanarak artıyor ve bu da bize ciddi bir zaman kaybı olarak geri dönüyor. Project Euler problemlerindeki amacı hatırlayın! Burada amacımız, çözüm üretmekten ziyade, etkili bir çözüm üretmek. Yazdığımız program, birkaç dakika içerisinde çözümü bulmalı. Eğer kaba kuvvetle bu problemi çözmeye kalksaydınız, işler zorlaşacaktı. Kaldı ki, ilerleyen problemlerde telaffuz edemeyeceğimiz basamaklarda işlemler yapmamız gerekecek! Bu yüzden akıllıca metotlar geliştirip, işlemlerimizi hızlandırmalı, kalabalıktan kurtulmalıyız.

Eratosthenes'in eleği algoritması, bu konuda imdadımıza yetişiyor. Daha önce kullandığımız gibi algoritmamız;

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;
}

şeklindedir. Bu noktadan sonra yapmamız gereken çok basit. Bu algoritma bize, kaça kadar olan asal sayıları bulmamızı istediğini soruyor. İsterseniz kaçıncı olarak da düzeltebilirsiniz ya da kaba bir yaklaşım uygulayarak, tahmini bir sayı belirler ve muhtemelen bu sayıya kadar, bu kadar asal sayı olur dersiniz. Ben burada 200.000'e kadar olan asal sayıları bir diziye aktararak, 10.001. asal sayının ne olduğuna bakmayı tercih ettim. Fakat bunun etkili bir yöntem olmadığını tekrar belirtmek isterim. Sadece cevaba ulaşacağımı biliyordum ve her türlü hızlı olacaktı. Fakat söz konusu ilerleyen problemlerde, gereken özeni göstermek gerekecek.

ArrayList primes = SieveOfEratosthenes(200000);

Console.WriteLine(primes[10000]);

Ögetay Kayalı

Ögetay Kayalı

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

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