Eratosfen elagi

Vikipediya, ochiq ensiklopediya
Eratosfen algoritmiga asosan 120gacha boʻlgan tub sonlarni topish animatsiyasi

Eratosfen elagi (Eratosfen gʻalviri) — butun son ngacha 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.

Algoritm[tahrir]

Butun son ngacha boʻlgan barcha tub sonlarni topish Eratosfen uslubiga asosan quyidgai bosqichlardan iborat.

  1. Ikkidan boshlab ngacha boʻlgan barcha sonlarni yozib chiqamiz (2, 3, 4, …,n).
  2. Oʻzgaruvchi p boshida 2 — birinchi butun songa teng deb qabul qilamiz.
  3. Yozib chiqilgan sonlardan pdan boshlab p qadam bilan ngacha barcha sonlarni oʻchiramiz, (yaʼni 2p, 3p, 4p, … kabi sonlar).
  4. pda katta birinchi oʻchilirilmagan sonni p deb yangidan qabul qilamiz.
  5. 3- va 4-qadamni p2 qiymati ndan katta yoki teng boʻlguncha takrorlaymiz.

Natijada roʻyhatdagi oʻchirilmagan sonlarning barchasi tub son boʻladi.

Amaliyotda, ushbu algoritmni quyidagicha yaxshilash (tezlashtirish) mumkin. Algoritmdagi 3-qadamda sonlarni p2 dan boshlab oʻchirish yetarli, chunki bundan kichik sonlar avval oʻchirilgan boʻladi. Va, algoritm p2 qiymati nga teng yoki katta boʻlganda toʻxtatiladi.

Misol[tahrir]

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ʻyhatdagi birinchi son 2 — butun son. Roʻyhatdan birma-bir 2ning koʻpaytmalarini oʻchirib chiqamiz, yaʼni 2 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ʻyhatdan endi 3ning koʻpaytmalarini oʻchirib chiqamiz, yaʼni 3 2=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ʻyhatdan endi 5 ning koʻpaytmalarini oʻchirib chiqamiz, yaʼni 52=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 p2 >= n shart bajarilguncha oʻchirib chiqish zarur. misol uchun, 5ning koʻpaytmalari oʻchirilib chiqildi va 62 > 30 shart bajarildi. Demak, oʻchirilmagan sonlarning barchasi butun son:

 2  3     5     7           11    13          17    19          23                29   

C tilidagi dastur[tahrir]

 /*
 * Eratosfen Elagi
 * soe_algo.c
 */
#include <stdio.h>
#include <stdbool.h>
#include <math.h>
 
int main (int argc,char *argv[])
{
 
	if (argc<2) {
		printf("Ushbu dastur biror butun songacha bo'lgan tub sonlarni ko'rsatadi \n
			Foydalanish: %s <butun son> \n ", argv[0]);
		return -1;
	}
 
	int m, k,  upper_bound = atoi(argv[1]);
 
	int upper_bound_sqrt = (int) sqrt(upper_bound);
 
	bool is_composite[upper_bound + 1];
 
	for (m = 2; m <= upper_bound_sqrt; m++) {
		if (!is_composite[m]) {
			printf("%d ", m);
			for (k = m * m; k <= upper_bound; k += m)
				is_composite[k] = true;
		} // if
	}//for
 
	for (m = upper_bound_sqrt + 1; m <= upper_bound; m++)
		if (!is_composite[m])
			printf("%d ", m);
 
	printf("\n");
 
	return 0;
} // end