Mavzu: Tub va murakkab sonlar. Eratosfen g’alviri

Eyler elaklari. 

Eylerning zeta mahsulot formulasining isboti Eratosfen elakining versiyasini o'z ichiga oladi, unda har bir kompozitsion raqam bir marta yo'q qilinadi. Xuddi shu elak Gries & Misra (1978) tomonidan qayta kashf etilgan va chiziqli vaqt talab qilishi kuzatilgan . U ham 2 dan n gacha boʻlgan raqamlar roʻyxati bilan boshlanadi . Har bir qadamda birinchi element keyingi asosiy element sifatida aniqlanadi, ro'yxatning har bir elementi bilan ko'paytiriladi (shuning uchun o'zidan boshlanadi) va natijalar keyinchalik o'chirish uchun ro'yxatda belgilanadi. Keyin boshlang'ich element va belgilangan elementlar ish ketma-ketligidan chiqariladi va jarayon takrorlanadi:
[2] (3) 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 57 77 ...
[3] (5) 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 ...
[4] (7) 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 ...
[5] (11) 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 ...
[...]
Bu erda misol algoritmning birinchi bosqichidan keyin koeffitsientlardan boshlab ko'rsatilgan. Shunday qilib, k -bosqichda k - tutqichning qolgan barcha karralari ro'yxatdan o'chiriladi, bundan keyin ular faqat birinchi k tub sonlar bilan mos keladigan raqamlarni o'z ichiga oladi ( qarang. g'ildirak faktorizatsiyasi ), ro'yxat keyingisidan boshlanadi. tub va undagi birinchi element kvadratidan past bo'lgan barcha raqamlar ham tub bo'ladi.
Shunday qilib, chegaralangan tub sonlar ketma-ketligini yaratishda, keyingi aniqlangan tub yuqori chegaraning kvadrat ildizidan oshib ketganda, ro'yxatdagi qolgan barcha raqamlar tub sonlar hisoblanadi. Yuqorida keltirilgan misolda bu 11 ni keyingi tub son sifatida aniqlash orqali erishiladi, barcha tub sonlar roʻyxati 80 dan kichik yoki unga teng boʻladi.
Esda tutingki, qadam tashlab qo‘yiladigan raqamlar bu bosqichda ko‘paytmalarni belgilashda ham foydalaniladi, masalan, 3 ning karralari uchun bu 3 × 3 = 9 , 3 × 5 = 15 , 3 × 7 = 21 , 3 × ga teng. 9 = 27 , ..., 3 × 15 = 45 , ..., shuning uchun bu bilan shug'ullanishda ehtiyot bo'lish kerak.