Berilgan N sonigacha bo’lgan tub sonlarni topishning eng samarali algoritmi

Assalomu alaykum. Bugun sizlarga ajoyib bir algoritmni ko’rsatib o’tmoqchiman. Bu algoritmning nomi
Eretasfen G’alviri (ing Eratosthenes sieve, rus решето Эратосфена). Algoritmning asosiy maqsadi 1 dan n (n
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.

Tepada nega aynan 2,3,5,7… ga bo’linadigan sonlarni olganimizga tushunmagan bo’lsangiz hech ham tushkunlikka tushmang. Maqola oxirigacha bilib olasiz.

Keling n = 30 bo’lgandagi holatni bosqichma bosqich ko’rib chiqaylik:

1. Oldin 2 dan n gacha bo’lgan sonlardan 2 ga bo’linadiganlarni (2 dan tashqari) belgilab olamiz:
   
2. Endi esa 3 ga bo’linadiganlarini (3 dan tashqari) :
   

3. Bundan keyingi navbatda 5 ga bo’linadiganlarini (5 dan tashqari):
   

4. 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. Menimcha bu yerda nima bo’layotganini tushundingiz deb o’ylayman.

Nihoyat algoritmni kompyuter tiliga o’giramiz:Umuman bu algoritmni har xil usullarda dastur holiga keltirish mumkin.

Dastur matni (C++):

#include  
using namespace std; 
 //funksiya hosil qilamiz 
void tub_sonlar(int n){ 
     // [0..n] gacha bo'lgan boolean tipli massiv hosil qilamiz // massivning barcha qiymatlari true qiymatda bo'ladi. 
     // Dastur oxirida massivdagi true qiymatli indekslar tub sonlar , false qiymatli 
     // indekslar esa tubmas sonlar bo'ladi bool 
     bool prime[n+1]; // massivni tavsiflash    
     memset(prime, true, sizeof(prime)); //massivning barcha qiymatlarini true qilamiz 
     for (int p=2; p*p

	

	

	Dastur matni (Java):

	
//bunda ham huddi c++ dagiday ishlar bajariladi
class tublar{ 
    void tub_sonlar(int n){
         boolean prime[] = new boolean[n+1]; 
         for(int i=0;i

	Dasturning ishlashi : 
	O(n*log(log(n)))

	

	Bilimingizni mustahkamlash uchun quyidagi masalani ishlashingiz mumkin: Masala

	

	Menimcha algoritmni yaxshi tushuntira oldim deb o'ylayman.Kimgadir bu bilan foydam teggan bo'lsa men bundan xursandman. Agarda maqolada tushunmovchiliklar yoki xatoliklar bo'lsa bemalol maqolaning izohlar qismiga yoki Junior_coder ga murojaat qilishingiz mumkin. Zero "Qiyin narsa yo'q, Qiyin tushuntirish bor xolos"

	

	

	

	

	Foydalanilgan manbalar : algo.ubtuit.uz geeksforgeeks wikipedia