Eratosfen elagi

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

 Algoritm 
Butun son  gacha boʻlgan barcha tub sonlarni topish Eratosfen uslubiga asosan quyidagi bosqichlardan iborat.

 Ikkidan boshlab  gacha boʻlgan barcha sonlarni yozib chiqamiz (2, 3, 4, …, ).
 Oʻzgaruvchi  boshida 2 – birinchi butun songa teng deb qabul qilamiz.
 Yozib chiqilgan sonlardan  dan boshlab  qadam bilan  gacha barcha sonlarni oʻchiramiz, (yaʼni , , , … kabi sonlar).
 da katta birinchi oʻchilirilmagan sonni  deb yangidan qabul qilamiz.
 3- va 4-qadamni  qiymati dan katta yoki teng boʻlguncha takrorlaymiz.

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

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

 Misol 
Quyidga n=30 uchun Eratosfen algoritmni qoʻllab tub sonlarni topamiz. Buning uchun, dan gacha 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  – butun son.
Roʻyxatdan birma-bir ning 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ʻyxatdan 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  – butun son.
Roʻyxatdan 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 ning koʻpaytmalarini  >=  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 
 /*
 * 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

 Havolalar 
 Eratosfen elagi Encyclopaedia of Mathematics saytida  

Turkum:Algoritmlar