Yazan : Şadi Evren ŞEKER

Özellikle sayılar teorisinde (number theory) önemli bir yer tutan, kafes çözümlemelerde (lattice based solutions) birisidir. Bilgisayar bilimlerinde, özellikle veri güvenliği konusunda, şifreleme algoritmalarına saldırı için kullanılmaktadır.

Problem basitçe belirli bir üst sınıra kadar olan asal sayıları bulmayı hedefler (örneğin 30’a kadar olan asal sayıları bulmak istiyor olalım). Bu problemin çözümü için Eratosten (millatan önce 276, 194 yılları arası) tarafından ortaya atılan yöntem aşağıdaki şekildedir:

Öncelikle bütün sayı kümesini içeren bir tablo hazırlıyoruz. Bu tablodan eleme yoluyla bazı sayıları siliyoruz.

Örneğin aşağıdaki şekilde bir tablomuz olsun:

1 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 30

 

Bu tablodan sırasıyla sayı eleyerek asal sayıları elde edelim. Tek bilmemiz gereken ilk asal sayının 2 olduğudur. Dolayısıyla asal sayılar kümemizin ilk elemanını 2 olarak atıyoruz. Ayrıca 1 sayısının asal olmadığını da biliyoruz.

Bulunan asal sayılar : {2}

1 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 30

 

Yukarıdaki şekilde asal sayıları yeşil ve asal olmayan sayıları kırmızı ile işaretleyerek işe başlıyoruz. 2 sayısının asal olduğunu biliyorsak, 2nin katlarının asal olmadığını da biliyoruz demektir. Bu sayıları kalburdan eliyoruz.

1 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 30

Kalburda eleme yapıldıktan sonra kalan sayılardan sıradaki ilk sayı yine asaldır.

Bulunan asal sayılar : {2,3}

1 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 30

 

Bu sefer 3’ün katlarını eleyerek işleme devam ediyoruz.

1 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 30

 

Ardından kalburda kalan ilk sayıyı ilan edip işleme devam ediyoruz:

Bulunan asal sayılar: {2,3,5} ve 5’in katlarını da eliyoruz.

1 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 30

 

Bulunan asal sayılar : {2,3,5,7} ve 7’nin katları elenince kalburda değişiklik olmuyor.

Bulunan asal sayılar : {2,3,5,7,11} yine 11’in katları kalburda zaten elenmiş

Bulunan asal sayılar : {2,3,5,7,11,13} yine 13’ün katları kalburda zaten elenmiş

Bulunan asal sayılar : {2,3,5,7,11,13,17} yine sıradaki diğer bütün sayılar için eleme işlemi yapılmıştır ve listeye doğrudan ekleyebiliriz.

Bulunan asal sayılar : {2,3,5,7,11,13,17,19,23,29} kümesini bularak işlemi bitirebiliriz.

Yukarıdaki şekilde işlem tamamlanmış ve verilen sayıya kadar olan asal sayılar bulunmuş olunur. Burada ufak bir not, fermat’ın teorisine göre, aranan aralığın en büyük sayısı olan limit değerinin kareköküne kadar aramak yeterlidir. Örneğimizde limit 30 olduğu için , 30’un karekökü olan 6’ya kadar bakılması yeterlidir. Nitekim bu değerden sonra kalburda bir değişiklik olmadığı görülebilir.

Yorumlar

  1. nushaba

    10 kişilik bir grup her grupta en az bir kişi olmak koşuluyla kaç farklı şekilde 2 grupa bölünebilir?
    A) 128
    B) 256
    C) 511
    D) 1023
    E) 2048

    (doğru cevap C)511 kabul edilmiş)

    Matematikte kombinasyon/permütasyon problemleri gibi çözmeye çalıştım ama yapamadım.
    Yardımcı olursanız sevinirim

  2. Otvertka

    Nushaba sorunuzun matematiktutkusu isimli sitede,gereksizyorumcu isimli üye tarafından çözümünü aynen aktarıyorum;
    (Bahsi geçen siteye sorunuzu bırakmışsınız ancak tekrar aynı siteye erişemediğinizi varsayıp burada paylaşıyorum.)

    10 kişiden 1. grubu içinde 0 ve 10 kişi olmayacak şkilde 210-C(10,10)-C(10,0)=1022 şekilde seçebiliriz

    bir grup insanın 1. veya 2. grupta yanyana gelmesi farklı durumlar oluşturmayacağından bulşduğumuz bu sayıyı grup sayısının permütasyonlarına yani 2! e bölmeliyiz 1022/2=511 bana göre cevap bu olmalı.

nushaba için bir cevap yazın Cevabı iptal et

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