202-“kidt” guruhi talabasi Allaberganova Dilafro`zning algaritmlar va berilganlar strukturasi fanidan tayyorlagan mustaqil ishi mavzu: n gacha bo’lgan tub sonlarni topish. Erotasfen g`alviri. Topshirdi: Allaberganova Dilafro`z ­ Qabul qildi

Urganch Davlat Universiteti
202-“KIDT” guruhi talabasi Allaberganova Dilafro`zning algaritmlar va berilganlar strukturasi fanidan tayyorlagan
MUSTAQIL ISHI


Mavzu: N gacha bo’lgan tub sonlarni topish. Erotasfen g`alviri.
Topshirdi: Allaberganova Dilafro`z ­______
Qabul qildi: Yuldashov Allabergan ______
2022-yil
Nazariy ma`lumot:
Algoritmning asosiy maqsadi 1 dan n (n<10 mln)gacha bo'lgan barcha tub sonlarni topishdir. Avvalambor tub son nimaligini maktabdagi davrimizdan esimizga solib olaylik : Faqat 1 ga va o'ziga bo'linadigan sonlar tub sonlar deyiladi.
Demak tushuntirmoqchi bo'lgan algoritmning g'oyasi quyidagicha:
2 dan n gacha bo'lgan sonlarda 2 ga bo'linadiganlarni 2 dan tashqari, 3 ga
bo'linadiganlarni 3 dan tashqari, 5 ga
bo'linadiganlarni 5 dan tashqari. 7 ga
bo'linadiganlarni 7 dan tashqari...... sonlarni belgilab olamiz. Qarabsizki belgilanmay qolgan sonlarni tub sonlardir.
n = 30 bo'lgandagi holatni bosqichma bosqich ko'rib chiqaylik:

Oldin 2 dan n gacha bo'lgan sonlardan 2 ga bo'linadiganlarni (2 dan tashqari) belgilab olamiz:

	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

Endi esa 3 ga bo'linadiganlarini (3 dan tashqari) :

	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

Bundan keyingi navbatda 5 ga bo'linadiganlarini (5 dan tashqari):

	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

Qarab turganingizdek 7 dan keyingi bo'yalmay qolgan kataklardagi sonlar bo'linadigan boshqa bo'yalmagan kataklar yo'q. Ya'ni 7,11,13,17,19,23,29 ga bo'linadigan boshqa bo'yalmagan kataklar qolmadi.Shuning uchun keyingi bosqichlarda yana bo'yab ko'rsatishga hojat yo'q.

Endi esa nimaga aynan 2,3,5,7... larni bo'lib chiqayotganimga e'tiboringizni qaratsam.Tepadagi 1-bosqichdagi jadvalning 1-katagiga e'tiboringizni qaratsam. Katak bo'yalmagan . O'sha 2 turgan katakni biror a deb belgilab olsak. a+1 dan n gacha barcha 2 ga bo'linadiganlarni belgilab chiqamiz. Buni belgilab bo'lgandan so'ng keyingi (tepadagi 2-bosqich)katakni bo'yalgan yoki bo'yalmaganligini tekshirsak.. U bo'yalmagan.U katakda 3 turibdi. Endi o'sha 3 dan tashqari n gacha barcha 3 ga bo'linadigan sonlarni bo'yab chiqamiz. Yana tepadagi keyingi bosqichga o'tamiz. Endi 4 turgan katakchani tekshirsak u bo'yalgan ekan demak unga e'tibor bermay keyingi katakchaga o'tib ketishimiz kerak.

Dastur matni:
class tublar {
void tub_sonlar(int n) {
boolean prime[] = new boolean[n+1];
for(int i=0;i
if(prime[p] == true) { for(int i = p*2; i <= n; i += p) prime[i] = false;
}
}
for(int i = 2; i <= n; i++) { if(prime[i] == true) System.out.print(i + " ");
}
}
public static void main(String args[]) {
int n = 30; tublar g = new tublar(); g.tub_sonlar(n);
}
}


Dastur blok sxemasi: