Tub sonlar nazariyasi

Qadam-baqadam algoritm (Eratosfen reshetkasi)

1. 
   Tub sonlar aniqlanadigan yuqori chegara N kiritilsin.
   
2. 
   M massivning 2 dan N gacha bo’lgan elementlariga bir qiymati berilsin (barchasi tub sonlar deb faraz qilinadi).
   
3. 
   Biror bir K soniga karrali bo’lgan sonlarni o’chirishning yuqori chegarasi bo’lgan L = √N hisoblansin. Bu cheklash haqqoniydir, chunki N soni √N dan katta bo’lgan ikkita ko’paytuvchiga ajralishi mumkin emas.
   
4. 
   K = 2 qiymat berilsin.
   
5. 
   Tekshirilsin. Agar K > L ,bo’lsa 14-punktga o’tilsin.
   
6. 
   S = 2*K hisoblansin.
   
7. 
   K=2 uchun N = K, K>2 hollar uchun esa H=2*K qadam hisoblansin. Barcha K>2 lar uchun qadamning ikki marta oshirilishi dasturning ishlashini tezlashtiradi va natijaning o’zgarishiga olib kelmaydi. Chunki N qadam bilan K ga karrali murakkab sonlar o’chiriladi. 2 dan boshqa barcha tub sonlar toq bo’lganligi uchun ham, toq songa toq son qo’shilganda natija juft son bo’ladi. Barcha juft sonlar birinchi bosqichda 2 ga karrali sonlarni aniqlashda o’chirilgan bo’ladi. Ularni qaytadan o’chirish xato bo’lmadi, ammo dasturning ishlash vaqti oshadi xolos.
   
8. 
   Tekshirilsin. Agar S > N bo’lsa 12-punktga o’tilsin.
   
9. 
   M[S] = 0 bajarilsin.
   
10. 
    S ning qiymati H qadamga oshirilsin : S = S + H.
    
11. 
    8- punktga o’tilsin.
    
12. 
    K ning qiymati 1 birlikga oshirilsin: K = K + 1.
    
13. 
    5- punktga o’tilsin.
    
14. 
    M jadvalning 2 do N gacha bo’lgan elementlari bosib chiqarilsin, bu erda M[K] = 1.
    

3. Blok-sxema