Mavzu: Tub va murakkab sonlar. Eratosfen g’alviri

Incremental elak.

Elakning qoʻshimcha formulasi tub sonlar avlodini ularning koʻpaytmalari avlodi bilan aralashtirish orqali cheksiz (yaʼni, yuqori chegarasiz) tub sonlarni hosil qiladi (shunda tub sonlarni koʻpaytmalar orasidagi boʻshliqlarda topish mumkin), bunda Har bir tub p soni to'g'ridan-to'g'ri tubning kvadratidan p ga (yoki toq tub sonlar uchun 2 p ) bosqichma-bosqich sanash orqali hosil bo'ladi. Samaradorlikka salbiy ta'sir ko'rsatmaslik uchun generatsiya faqat bosh kvadratga yetgandan so'ng boshlanishi kerak. U ma'lumotlar oqimi paradigmasi ostida ramziy ravishda ifodalanishi mumkin
tub sonlar = [ 2 , 3 , ...] \ [[ p ², p ²+ p , ...] tub sonlarda p ]
,
raqamlarning arifmetik progressiyalarining to'plamini ayirishni bildiruvchi ro'yxatni tushunish belgisidan foydalanish . \
Bosh sonlarni ketma-ket tub sonlar orqali boʻlinish testi orqali kompozitlarni iterativ ravishda elakdan oʻtkazish yoʻli bilan ham hosil qilish mumkin . Bu Eratosthenes elak emas, lekin ko'pincha u bilan aralashtirib yuboriladi, garchi Eratosthenes elaklari ularni sinash o'rniga to'g'ridan-to'g'ri kompozitsiyalarni ishlab chiqaradi. Sinov bo'linishi boshlang'ich diapazonlarni yaratishda Eratosfen elakidan ko'ra yomonroq nazariy murakkablikka ega. 
Har bir tub sonni sinovdan o'tkazishda optimal sinov bo'linishi algoritmi kvadrat ildizidan oshmaydigan barcha tub sonlardan foydalanadi, Eratosfen elak esa har bir kompozitsiyani faqat tub omillaridan ishlab chiqaradi va kompozitsiyalar orasida "bepul" tub sonlarni oladi. Devid Tyorner  tomonidan 1975 yilda keng ma'lum bo'lgan funktsional elak kodi ko'pincha Eratosthenes elakiga misol sifatida taqdim etiladi, lekin aslida suboptimal bo'linish elakidir.

Algoritmik murakkablik.

Eratosthenes elaklari kompyuterning ishlashini baholashning mashhur usulidir. Tasodifiy kirish mashinasi modelida n dan past boʻlgan barcha tub sonlarni hisoblashning vaqt murakkabligi O ( n log log n ) amallardir, bu asosiy garmonik qatorning log log n ga asimptotik tarzda yaqinlashishining bevosita natijasidir . U kirish hajmiga nisbatan eksponensial vaqt murakkabligiga ega, bu esa uni psevdo-polinomli algoritmga aylantiradi. Asosiy algoritm O ( n ) xotirani talab qiladi.
Algoritmning bit murakkabligi O ( n ( log n ) (log log n ) ) xotira talabi bilan O ( n ) bit operatsiyalari .
Odatda amalga oshiriladigan sahifa segmentlangan versiyasi segmentlanmagan versiya bilan bir xil operatsion murakkabligi O ( n log log n ) ga ega, lekin bo'sh joy talablarini segment sahifasining juda minimal o'lchamiga va asosiy asosiy sonlarni saqlash uchun zarur bo'lgan xotiraga nisbatan qisqartiradi. Oʻlchamdagi ketma-ket sahifa segmentlaridan kompozitlarni ajratish uchun ishlatiladigan diapazonning kvadrat ildizi (√ n/log n) .
Eratosthenes elakining maxsus (kamdan-kam hollarda amalga oshirilgan) segmentlangan versiyasi, asosiy optimallashtirishlari bilan O ( n ) operatsiyalari va O ( √ n ) dan foydalanadi.log jurnali n/log n) xotira bitlari. Katta O belgisidan foydalanish amaliy diapazonlar uchun juda muhim bo'lishi mumkin bo'lgan doimiy omillar va ofsetlarni e'tiborsiz qoldiradi: Pritchard g'ildiragi elak deb nomlanuvchi Eratosfen elakining ishlashi O ( n ) ga ega , lekin uning asosiy amalga oshirilishi. foydalanish mumkin bo'lgan diapazonni mavjud xotira miqdori bilan cheklaydigan "bitta katta massiv" algoritmini talab qiladi, aks holda xotiradan foydalanishni kamaytirish uchun sahifani segmentlarga bo'lish kerak. Xotirani saqlash uchun sahifa segmentatsiyasi bilan amalga oshirilganda, asosiy algoritm hali ham taxminan O (n/log n) xotira bitlari ( O () yordamida Eratosthenesning asosiy sahifa segmentlangan elaklari talabidan ancha ko'p.√ n/log n) xotira bitlari). Pritchardning ishi xotira talabini katta doimiy omil hisobiga kamaytirdi. Olingan g'ildirakli elak O ( n )ishlashi va maqbul xotira talabiga ega bo'lsa-da, u amaliy elakdan o'tkazish diapazonlari uchun Eratosthenesning asosli g'ildirak faktorizatsiyalangan asosiy elakidan tezroq emas.