Pages

17/12/2023

Erotosfen g'alviri

 Eratosfen gʻalviri (Eratosfen elagi) — n natural songacha boʻlgan barcha tub sonlarni topish algoritmi boʻlib, qadimiy grek matematigi Eratosfen Kireniy sharafiga nomlangan. 

Eratosfen elagi algoritmi kichik (odatda 10 milliondan kichik boʻlgan) tub sonlarni topishning eng tez usuli hisoblanadi.

Avvalambor tub son nimaligini esimizga solib olaylik: faqat 1 ga va oʻziga boʻlinadigan natural sonlar tub sonlar deyiladi.

Quyida n = 30 uchun Eratosfen gʻalvirini qoʻllab tub sonlarni toping. 

1. Buning uchun, 2 dan 30 gacha boʻlgan barcha butun sonlarni tartib boʻyicha yozib

chiqamiz:

2. 2 dan 30 gacha boʻlgan sonlardan 2= 4 dan boshlab 2 ga boʻlinadiganlarni (2 dan

tashqari, chunki 2 tub son) oʻchirib chiqamiz.

3. Keyingi oʻchirilmagan son 3. Roʻyxatdan 3 = 9 dan boshlab 3 ga boʻlinadiganlarini

(3 dan tashqari, chunki 3 tub son) oʻchirib chiqamiz.

4. Roʻyxatdan endi 5 = 25 dan boshlab 5 ga boʻlinadiganlarini (5 dan tashqari, chunki 5 tub son) oʻchirib chiqamiz.

5. Jarayonni shu yerda toʻxtatamiz. Chunki 7 > 30. 


2345678910
11121314151617181920
21222324252627282930

Demak, o'chirilmay qolgan sonlar: 2; 3; 5; 7; 11; 13; 17; 19; 23; 29 tub sonlar.

Комментариев нет:

Отправить комментарий