Eratosfen elagi

Fayl:Animation Sieve of Eratosthenes.gif

Eratosfen algoritmiga asosan 120 gacha boʻlgan tub sonlarni topish animatsiyasi

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

Algoritm

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

1. Ikkidan boshlab Andoza:Math gacha boʻlgan barcha sonlarni yozib chiqamiz (2, 3, 4, …, Andoza:Math).
2. Oʻzgaruvchi Andoza:Math boshida 2 – birinchi butun songa teng deb qabul qilamiz.
3. Yozib chiqilgan sonlardan Andoza:Math dan boshlab Andoza:Math qadam bilan Andoza:Math gacha barcha sonlarni oʻchiramiz, (yaʼni Andoza:Math, Andoza:Math, Andoza:Math, … kabi sonlar).
4. Andoza:Mathda katta birinchi oʻchilirilmagan sonni Andoza:Math deb yangidan qabul qilamiz.
5. 3- va 4-qadamni Andoza:Math qiymati Andoza:Mathdan 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 Andoza:Math dan boshlab oʻchirish yetarli, chunki bundan kichik sonlar avval oʻchirilgan boʻladi. Va, algoritm Andoza:Math qiymati Andoza:Mathga teng yoki katta boʻlganda toʻxtatiladi.

Misol

Quyidga n=30 uchun Eratosfen algoritmni qoʻllab tub sonlarni topamiz. Buning uchun, Andoza:Mathdan Andoza:Mathgacha 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 Andoza:Math – butun son. Roʻyxatdan birma-bir Andoza:Mathning 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 Andoza:Math – 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 Andoza:Mathning koʻpaytmalarini Andoza:Math >= Andoza:Math shart bajarilguncha oʻchirib chiqish zarur. Andoza:Math 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   

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 Andoza:Ref-en