AlgoritmalarMatematik

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;

[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ı

Etiketler

Ögetay Kayalı

Rasyonalist kurucu, editör ve yazar. Michigan Tech. Üniversitesi Fizik bölümünde araştırma görevlisi olarak doktorasını yapmaktadır. Öncesinde Ege Üni. Astronomi bölümünden birincilikle mezun olup burada bir yıl kozmoloji üzerine yüksek lisans yapmıştır. Ayrıca İzmir Biyotıp ve Genom Enstitüsünde, Moleküler Biyoloji ve Genetik bölümünde bir yıl yüksek lisansını gerçekleştirdiği sırada lazerli biyofotonik görüntüleme teknikleri üzerine çalışmalarda bulunmuştur.

Bir cevap yazın

Başa dön tuşu
Kapalı
Kapalı