İ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;
[snippet id=”259″]ş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.
[snippet id=”616″]Ögetay Kayalı
