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<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.

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 <bits/stdc++.h> 
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<=n; p++) { 
        // agar prime[p] ning qiymati o'zgartirilmagan bo'lsa u tub son 
        if (prime[p] == true) { 
            // barcha p ga bo'linadiganlarini false qilamiz. Chunki ular tub bo'lmaydi 
            //tepadagi tushuntirish misoli sifatida bo'yaymiz desak to'g'riroq bo'ladi 
            for (int i=p*2; i<=n; i += p) 
                prime[i] = false; } 
            }    
     // massivdagi qiymati true bo'lgan indekslarni chiqaramiz . Chunki ular tub sonla     r 
    for (int p=2; p<=n; p++) 
        if (prime[p]) cout << p << " "; 
}   
//Asosiy qismi 
int main() {
 //n = 30 sifatida ko'ramiz 
    int n = 30; 
    cout << "Quyidagilar " << n <<" gacha bo'lgan tub sonlar:"<<'\n';
     tub_sonlar(n); 
return 0; 
}

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<n;i++)
             prime[i] = true; 
        for(int p = 2; p*p <=n; p++){ 
            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); 
    } 
}

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