2, 3, 4, 5, 9,10, 25ga bo`linish alomatlari. Ta’rif

Eratosfen g’alviri.

Eratosfen gʻalviri — butun son{\displaystyle n}gacha boʻlgan barcha tub sonlarni topish algoritmi boʻlib, qadimiy Grek matematigi Eratosfen Kireniyga bagʻishlab nomlangan. Eratosfen elagi algoritmi kichik (odatda, 10 milliondan kichik boʻlgan) tub sonlar topishning eng tez uslub hisoblanadi.

Quyidga n=30 uchun Eratosfen algoritmni qoʻllab tub sonlarni topamiz. Buning uchun, 2dan 30gacha boʻlgan barcha butun sonlarni tartib boʻyicha yozib chiqamiz:

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
Roʻyxatdagi birinchi son 2 — butun son. Roʻyxatdan birma-bir 2ning koʻpaytmalarini oʻchirib chiqamiz, yaʼni 2 ² = 4 dan boshlab :
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
Keyingi oʻchirilmagan son 3 — butun son. Roʻyxatdan endi 3ning koʻpaytmalarini oʻchirib chiqamiz, yaʼni 3 ²=9 dan boshlab :
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
Keyingi oʻchirilmagan son 5 — butun son. Roʻyxatdan endi 5 ning koʻpaytmalarini oʻchirib chiqamiz, yaʼni 5²=25 dan boshlab :
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
Algoritmga asosan pning koʻpaytmalarini p² >= n shart bajarilguncha oʻchirib chiqish zarur. misol uchun, 5ning koʻpaytmalari oʻchirilib chiqildi va 6² > 30 shart bajarildi. Demak, oʻchirilmagan sonlarning barchasi butun son:
2 3 5 7 11 13 17 19 23 29

4.