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 22 = 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 32 = 9 dan boshlab 3 ga boʻlinadiganlarini
(3 dan tashqari, chunki 3 tub son) oʻchirib chiqamiz.
4. Roʻyxatdan endi 52 = 25 dan boshlab 5 ga boʻlinadiganlarini (5 dan tashqari, chunki 5 tub son) oʻchirib chiqamiz.
5. Jarayonni shu yerda toʻxtatamiz. Chunki 72 > 30.
| 2 | 3 | 5 | 7 | ||||||
| 11 | 13 | 17 | 19 | ||||||
| 23 | 29 |
Demak, o'chirilmay qolgan sonlar: 2; 3; 5; 7; 11; 13; 17; 19; 23; 29 tub sonlar.
Комментариев нет:
Отправить комментарий