Eratosten elagi
Eratosten elagi haqida bilib oling
Kirish
Bizga sonlar oralig‘i berilgan va biz ushbu oraliqdagi barcha tub sonlarni topishimiz kerak.
Masalan, quyidagi oraliqda
tub sonlar:
Eratosten elagi haqida bilib oling
Bizga sonlar oralig‘i berilgan va biz ushbu oraliqdagi barcha tub sonlarni topishimiz kerak.
Masalan, quyidagi oraliqda
tub sonlar:
Ushbu vazifa uchun klassik algoritm — Eratosten elagi.
Oraliqdagi sonlarni qayta ishlash jarayonida, joriy tub sonning barcha karralilarini darhol murakkab (tub bo‘lmagan) deb belgilashimiz mumkin.
Masalan:
2 ni qayta ishlaganimizda, 2 ning barcha karralilarini murakkab deb belgilashimiz mumkin;3 ni qayta ishlaganimizda, 3 ning barcha karralilarini murakkab deb belgilashimiz mumkin;Bu bizga barcha tub bo‘lmagan sonlarni bosqichma-bosqich olib tashlash imkonini beradi.
Muhim faktni eslang: agar soni murakkab bo‘lsa, unda uning dan katta bo‘lmagan tub bo‘luvchisi mavjud.
Shuning uchun, gacha bo‘lgan barcha tub sonlarni topish uchun elash jarayonini faqat gacha bo‘lgan sonlar bilan bajarish kifoya.
Biz prime massivini yaratamiz, bunda:
prime[x] = true degani x hozircha tub deb hisoblanadi;prime[x] = false degani x murakkab.Dastlab, 0 va 1 dan tashqari barcha sonlar tub deb belgilanadi.
So‘ng 2 dan gacha bo‘lgan har bir i soni uchun:
i hali ham tub deb belgilangan bo‘lsa, unda i ning barcha karralilarini murakkab deb belgilang.Ichki sikl dan boshlanadi, chunki i ning undan kichik barcha karralilari avvalroq qayta ishlangan bo‘ladi.
Masalan, agar biz i = 5 da bo‘lsak, unda:
10 = 2 \cdot 5 2 ni qayta ishlashda allaqachon belgilangan;15 = 3 \cdot 5 3 ni qayta ishlashda allaqachon belgilangan;20 = 4 \cdot 5 bundan ham oldinroq belgilangan.Shuning uchun belgilashimiz kerak bo‘lgan birinchi yangi karrali .
Ba’zi masalalarda qiymati int turidan oshib ketishi (overflow) mumkin.
Bunday hollarda, ko‘paytirishdan oldin i ni long long ga o‘tkazish xavfsizroq.
Masalan:
int n;
vector<bool> prime(n + 1, true);
prime[0] = prime[1] = false;
for (int i = 2; i * i <= n; ++i) {
if (prime[i]) {
for (int j = i * i; j <= n; j += i) {
prime[j] = false;
}
}
}
for (int i = 2; 1LL * i * i <= n; ++i) {
...
}