Mavzu: Tub va murakkab sonlar. Eratosfen g’alviri

Psevdokod. 

Eratosfen elakini psevdokodda quyidagicha ifodalash mumkin:
algoritm Eratosthenes elegi kiritiladi
: butun son n > 1.
chiqish : 2 dan n gacha bo'lgan barcha tub sonlar .


A s 2 dan n gacha butun son bilan indekslangan mantiqiy qiymatlar massivi bo‘lsin ,
dastlab hammasi rostga o'rnatiladi .
i = 2, 3, 4, ... uchun , √ n dan oshmasligi kerak
, agar A [ i ] j = i ² , i ² + i , i ² +2 i , i ² +3 i , .. uchun toʻgʻri boʻlsa, bajaring. ., n dan oshmaydigan do A [ j ] := false

Barcha i ni shunday qaytaringki , A [ i ] rost bo'lsin .

Bu algoritm n dan katta bo'lmagan barcha tub sonlarni hosil qiladi . U umumiy optimallashtirishni o'z ichiga oladi, ya'ni i ² dan har bir tub i ning ko'paytmalarini sanashni boshlashdir . Ushbu algoritmning vaqt murakkabligi O ( n log log n ) , , agar massivni yangilash odatda bo'lgani kabi O (1) operatsiyasi bo'lsa.

Segmentli elak.

Sorenson ta'kidlaganidek, Eratosthenes elak bilan bog'liq muammo uning bajaradigan operatsiyalar sonida emas, balki uning xotira talablarida. Katta n uchun asosiy sonlar diapazoni xotiraga sig‘masligi mumkin; yomoni, hatto mo''tadil n uchun ham , uning keshdan foydalanish juda suboptimaldir. Algoritm butun A massivi bo'ylab yuradi , deyarli hech qanday mos yozuvlar joyini ko'rsatmaydi .
Ushbu muammolarni hal qilish segmentlangan elaklar tomonidan taklif etiladi, bu erda bir vaqtning o'zida diapazonning faqat qismlari elakdan o'tkaziladi. Bular 1970-yillardan beri maʼlum va quyidagicha ishlaydi:

1. 
   2 dan n gacha bo'lgan diapazonni D ≤ √ n o'lchamdagi segmentlarga ajrating .
   
2. 
   Oddiy elakdan foydalanib, birinchi (ya'ni eng past) segmentdagi tub sonlarni toping.
   
3. 
   Quyidagi segmentlarning har biri uchun ortib borayotgan tartibda, m segmentning eng yuqori qiymati bo‘lgan holda, undagi tub sonlarni quyidagicha toping:
   
   1. 
      D o'lchamdagi mantiqiy massivni o'rnating va
      
   2. 
      Massivdagi har bir tub p ≤ √ m sonining shu paytgacha topilgan koʻpaytmalariga mos keladigan oʻrinlarni tub boʻlmagan deb belgilang, m - D va m orasidagi p ning eng kichik karralisini hisoblab, uning karralarini odatdagidek p bosqichlarida sanab oʻting. Qolgan pozitsiyalar segmentdagi tub sonlarga mos keladi, chunki segmentdagi tubning kvadrati segmentda emas ( k ≥ 1 uchun bittasi bor{\displaystyle (k\Delta +1)^{2}>(k+1)\Delta} ).
      

Agar D √ n qilib tanlansa , algoritmning fazoviy murakkabligi O ( √ n ) ga teng, vaqt murakkabligi esa oddiy elakniki bilan bir xil bo‘ladi.
Yuqori chegarasi n shunchalik katta bo'lgan diapazonlar uchun Eratosthenesning sahifa segmentlangan elaklari talab qilganidek, √ n dan past bo'lgan elaklar xotiraga sig'maydi, uning o'rniga Sorenson elakiga o'xshash sekinroq, lekin joyni tejaydigan elakdan foydalanish mumkin.