Eratosthenes’in Eleği – Asal Sayı Algoritması

Eratosthenes’in eleği, parlak bir Yunan matematikçi olan Eratosthenes tarafından formüle edilen ve çabaları asal sayıların belirlenmesine büyük katkı sağlayan bir tekniktir.

Matematiğe çok şey kattı ve eleğin keşfi bu alanda yaptığı en iyi şeydi. Bir senaryoya uymayan sayıları eleyerek çalışan bir kalıp veya algoritmadır.

Eratosthenes’in eleği nedir?

Eratosthenes’in eleği, iki sayı kümesi arasındaki asal sayıları bulmaya yönelik matematiksel bir algoritmadır.

Eratosthenes’in eleği modelleri, belirli bir kriteri karşılamayan verilen sayıları eleyerek veya eleyerek çalışır. Bu durumda model, bilinen asal sayıların katlarını elemektedir.

Asal Sayı Algoritması

Asal sayı, sadece 1’e ve kendisine bölünebilen pozitif bir tam sayı veya 1’den büyük bir tam sayıdır. Asal sayı algoritması, bileşik sayıları eleyerek veya kaldırarak asal sayıları bulmak için kullanılan bir programdır. Algoritma, karmaşık döngülü bölme veya çarpma işlemlerini ortadan kaldırarak çalışmayı kolaylaştırır.

Aşağıda, verilen bir η tamsayısına eşit veya daha küçük asal sayıları bulmak için kullanılan adımlar verilmiştir.

• 2’den η’ye kadar olan tüm ardışık sayıları listeleyin, yani (2, 3, 4, 5, ……, η).
• İlk asal sayı harfini atayın p.
• ile başlayan p²‘nin bir artışını gerçekleştirin. p ‘ye eşit veya daha büyük tamsayıları işaretleyin. p² algoritmada. Bu tamsayılar şunlar olacaktır p(p + 1), p(p + 2), p(p + 3), p(p + 4) …
• ‘den büyük olan ilk işaretlenmemiş sayı p listeden tanımlanır. Numara listede mevcut değilse, prosedür durdurulur. p sayıya eşitlenir ve 3. adım tekrarlanır.
• Eratosthenes’in eleği, test edilen sayının karesi listedeki son sayıyı aştığında durdurulur.
• Algoritma sona erdiğinde listede işaretlenmemiş olarak kalan tüm sayılar asal sayı olarak adlandırılır.

Örnek 1

30’dan küçük veya eşit tüm asal sayıları doldurun.

Çözüm

• 1. Adım: İlk adım tüm numaraları listelemektir.

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29 ve 30.

• Adım 2: Yazın cesur 2’nin kendisi hariç, 2’nin tüm katları.

2, 3, 4, 5, 6 , 7 , 8, 9, 10,11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, ve 30.

• Adım 3: Bir sonraki gölgesiz sayı 3. Karesini yazın (3² = 9) kalın harflerle yazılmıştır.

2, 3, 4, 5, 6 , 7 , 8, 9, 10,11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, ve 30.

• Adım 4: Şimdi üçüncü gölgesiz sayı 5’tir. 5’in karesini yazın²=25 kalın yazılmıştır.

2, 3, 4, 5, 6 , 7 , 8, 9, 10,11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, ve 30.

• Adım 5: Gölgesiz dördüncü sayı 7’dir ve 30’un karekökünden büyüktür.
  Dolayısıyla, 2 ve 3 tarafından sırasıyla 14, 28 ve 21 olarak elendikleri için 7’nin katı kalmamıştır. Geriye kalan 2, 3, 5, 7, 11, 13, 17, 19, 23 ve 29 sayıları asaldır.

Örnek 2

Eratosthenes algoritmasını kullanarak 1 ile 100 arasındaki asal sayıları bulun.

Çözüm

1. Adım 1: 1 ile 100 arasındaki sayılar aşağıdaki tabloda listelenmiştir.

• 2. Adım: Bir sonraki adım, aşağıdakileri yazmaktır cesur 2’nin kendisi hariç, 2’nin tüm katları.

• 3. Adım: Şimdi cesur 3, 5 ve 7’nin tüm katları ve sadece bu sayıları bırakın.

• Adım 4: 11, 13, 17 ve 19’un katları listede bulunmadığından, 1 asal olmadığı için son olarak gölgelendirilir.

• Adım 5: Gölgesiz sayılar asaldır. Bunlar şunları içerir:

2, 3, 5,7, 11, 13,17,19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 ve 97.