Yazan : Şadi Evren ŞEKER

Belirli bir aralıkta verilen bütün asal sayıları bulmaya yarayan algoritmadır. Bu algoritmada bir kalbur problemi olarak görülebilir ve daha önceden problemle uğraşmış olan Eratosten tarafından geliştirilen çözümün gelişmiş halidir.

Algoritmanın ismi, 2004 yılında bu yöntemi geliştiren kişiden gelmektedir.

Algoritma adımları aşağıda açıklanmıştır:

  • Öncelikle bütün sayılar mod 60 ta çalışır. Yani sonuçlar 60’a bölümden kalan olarak değerlendirilecektir.
  • Sistemdeki bütün sayılar (x ve y dahil olmak üzere) pozitif tam sayılardır
  • Sistemdeki sayılar asal veya değil (bu yazıda a ve d harfleri kullanılacaktır) olarak işaretlenebilir
  • Kalbur listesindeki bir işaretin tersinin alınması a->d veya d->a dönüşümünün yapılması demektir.
  • Listenin ilk 3 elemanı, 2,3 ve 5 sayılarıdır.

Yukarıdaki bu ön tanımlardan sonra algoritmaya geçebiliriz:

Bir liste oluşturarak başlıyoruz. Asal sayıların bulunması istenen aradaki bütün sayılar bu listede bulunuyor ve ilk başta bütün sayılar, asal değil anlamında d olarak işaretleniyor.

Listedeki her sayının sırayla mod 60 sonucu bulunuyor. Sırayla bulunan değere n dersek,

  • Bu değerin {1,13,17,29,37,41,49,53} küme elemanlarından birisi olması halinde 4x2+y2 = n sonucu veren bütün çözümler ters çevrilir.
  • Kalan değeri {7,19,31,43} kümesinde ise 3x2 + y2 = n sonucu veren bütün çözümler ters çevrilir.
  • Kalan değeri {11,23,47,59} kümesinde ise 3x2 – y2 = n sonucu veren bütün çözümler ters çevrilir.

Yukarıdaki algoritmada bulunan kümelerin bir özelliği vardır. İlk kümedeki değerler, mod 12 için 1 veya 5 veren değerlerdir. İkinci küme mod 12 için 7 ve üçüncü küme mod 12 için 11 sonucunu verir.

Yukarıdaki algoritmanın çalışmasını bir örnek üzerinden anlamaya çalışalım:

40’a kadar olan asal sayıları yukarıdaki yöntemle bulmak istiyor olalım.

x = 1 ve y = 1 durumu ile çalışmaya başlıyoruz. Denklemde yerine yazarsak

4x2+y2 = n denklemi için n = 5 bulunur. Bu değer mod 12’de 5’tir ve ilk kümeye girer. Dolayısıyla 5 için asal işaretlemesi yapılır.

3x2 + y2 = n denklemi için n = 4 bulunur. Bu değer mod 12’de 7 olmadığı için bir işlem yapılmaz.

3x2 – y2 = n denkleminde n = 2 bulunur ve mod 12’de 11 olmadığı için bir işlem yapılmaz.

Yukarıdaki sorgulama işlemini x ve y değerlerini arttırarak tekrarlıyoruz.

x=1 ve y = 2 için işlemler yapıldığında sadece ikinci denklem sağlanır:

3x2 + y2 = n denklemi için n = 7 bulunur. Bu değer de mod 12’de 7 olduğu için 7 sayısı asal olarak işaretlenir.

Geri kalan sayılar için algoritmanın çalışması aşağıda tablo halinde verilmiştir.

x y 4x2+y2 4x2+y2 mod 12 3x2 + y2 3x2 + y2 mod 12 3x2 – y2 3x2 – y2 mod 12
1 1 5 5 4 4 2 2
1 2 8 8 7 7 -1 -1
1 3 13 1 12 0 -6 -6
1 4 20 8 19 7 -13 -1
1 5 29 5 28 4 -22 -10
1 6 40 4 39 3 -33 -9
2 1 17 5 13 1 11 11
2 2 20 8 16 4 8 8
2 3 25 1 21 9 3 3
2 4 32 8 28 4 -4 -4
2 5 41 5 37 1 -13 -1
2 6 52 4 48 0 -24 0
3 1 37 1 28 4 26 2
3 2 40 4 31 7 23 11
3 3 45 9 36 0 18 6
3 4 52 4 43 7 11 11
3 5 61 1 52 4 2 2
3 6 72 0 63 3 -9 -9
4 1 65 5 49 1 47 11
4 2 68 8 52 4 44 8
4 3 73 1 57 9 39 3
4 4 80 8 64 4 32 8
4 5 89 5 73 1 23 11
4 6 100 4 84 0 12 0
5 1 101 5 76 4 74 2
5 2 104 8 79 7 71 11
5 3 109 1 84 0 66 6
5 4 116 8 91 7 59 11
5 5 125 5 100 4 50 2
5 6 136 4 111 3 39 3
6 1 145 1 109 1 107 11
6 2 148 4 112 4 104 8
6 3 153 9 117 9 99 3
6 4 160 4 124 4 92 8
6 5 169 1 133 1 83 11
6 6 180 0 144 0 72 0

Yukarıdaki tabloda renklendirilen değerler asal sayılardır ve bu değerlerin oluşturduğu küme aşağıdaki şekildedir:

{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}

Yukarıdaki kümede görülen bu değerler, aynı zamanda 2-40 arasındaki asal sayılar kümesidir.

Yukarıda anlatılan bu algoritmanın kodlaması C# dilinde, aşağıda verilmiştir:

Yukarıdaki kod, daha önceden tanımlı limit değişkeninde, asal sayıların bulunacağı aralığın tanımlı olduğu kabulü ile başlar. Burada verilen değere kadar iki iç içe döngü ile ( kodun 26. Ve 27. Satırlarında) bütün x ve y değerlerini dener. Burada dikkat edilecek bir husus, denemelerin limitin kareköküne kadar yapılıyor olduğudur. Daha fazla bilgi için Fermat’ın çarpanlara ayırma yöntemini okuyabilirsiniz.

Ardından kodun 29 ve 37 satırları arasında üç adet if kontrolü ile yukarıdaki şartların sağlanıp sağlanmadığı kontrol edilmiş, şayet sağlıyorsa bu değerin kalbur üzerinde (sieve) tersi alınmıştır. isPrime dizisi bu anlamda kalburun tutulduğu ve hangi sayıların asal olduğunun işaretlendiği dizidir.

Kodun 40-45. satırları arasında, bulunan asal sayıların karelerinin asal olmadığı işaretlenmiştir.

Son olarak asal sayılar listemize, önceden tanımlı olan 2,3 ve kalbur üzerinde bulunan sayılar eklenmiş ve işlem bitirilmiştir.

Problemin çözümü için C# kodunu buraya tıklayarak indirebilirsiniz.

 

 

Bir cevap yazın

E-posta hesabınız yayımlanmayacak. Gerekli alanlar * ile işaretlenmişlerdir