Нийлмэл тоо бүрийг хамгийн бага анхны хуваагчаар нь яг нэг удаа зурж, анхны тоонуудыг O(n) хугацаанд олдог шигшүүр.

IntermediateХугацаа: O(n)Санах ой: O(n)

Эхлээд жижиг бодлого

n = 12. Анхны тоонууд нь 2, 3, 5, 7, 11. Нийлмэл тоонуудын хамгийн бага анхны хуваагч: 4, 6, 8, 10, 12-т 2, харин 9-д 3.

Linear Sieve 12-ыг яг нэг удаа, i = 6 үед 6 × 2 гэж зурна. i = 4 үед 4 × 3-ыг зурахгүй, учир нь 3 нь lp[4] = 2-оос их.

Энгийн аргаас санаа руу

Sieve of Eratosthenes анхны тоо бүрийн үржвэрийг зурдаг тул 12-ыг 2-оор ч, 3-аар ч зурна. Нийт ажил нь O(n log log n).

Linear Sieve нийлмэл тоо бүрийг зөвхөн хамгийн бага анхны хуваагчаар нь зурна. x = i × p хэлбэрт p нь lp[i]-гаас их биш байхаар хязгаарлавал p үргэлж x-ийн хамгийн бага анхны хуваагч болно. Ингэснээр тоо бүр нэг л удаа зурагдаж, нийт O(n).

Нэр томьёо ба тэмдэглэгээ

lp[x]
x-ийн хамгийн бага анхны хуваагч. 0 бол хараахан хэн ч зураагүй.
pr[]
Олдсон анхны тоонуудын жагсаалт, өсөх дарааллаар.
cnt
Олдсон анхны тоонуудын тоо, pr-ын урт.
i × pr[j]
Зурж буй тоо. pr[j] ≤ lp[i] ба i × pr[j] ≤ n байх хооронд л зурна.
lp[2…11]
2
3
4
5
6
7
8
9
10
11
lp[12…21]
12
13
14
15
16
17
18
19
20
21
lp[22…30]
22
23
24
25
26
27
28
29
30
cnt = 0
pr: анхны тоонууд
хоосон

lp[x] нь x-ийн хамгийн бага анхны хуваагч. 2-оос 30 хүртэлх бүх тоонд lp бөглөнө. Гол санаа: нийлмэл тоо бүрийг яг нэг удаа, өөрийнх нь хамгийн бага анхны хуваагчаар зурна.

Алхам 1 / 41
Хурд
  • Одоогийн i
  • Сая зурсан
  • Нийлмэл тоо
  • Анхны тоо
  • Олдсон анхны тоо
Слайд 1 / 6

Илүү ухаалаг шигшүүр

Sieve of Eratosthenes 12-ыг 2 удаа зурдаг: 2-оор ч, 3-аар ч. Linear Sieve нийлмэл тоо бүрийг яг нэг удаа зурна. Мөн lp[x] буюу x-ийн хамгийн бага анхны хуваагчийг олно.

linear-sieve.cpp
#include <bits/stdc++.h>
using namespace std;
int n, cnt, lp[1000005], pr[100005];
int main() {
cin >> n;
for (int i = 2; i <= n; i++) {
if (lp[i] == 0) {
lp[i] = i, pr[cnt++] = i;
}
for (int j = 0; j < cnt && pr[j] <= lp[i] && i * pr[j] <= n; j++) lp[i * pr[j]] = pr[j];
}
for (int j = 0; j < cnt; j++) cout << pr[j] << ' ';
return 0;
}

Юунд хэрэгтэй вэ?

n хүртэлх бүх анхны тоо, мөн тоо бүрийн хамгийн бага анхны хуваагч lp[x]-ийг олно. lp ашиглан дурын тоог хурдан задална.

Яаж ажилладаг вэ?

1. i = 2 … n. lp[i] хоосон бол i анхны тоо: lp[i] = i болгоод pr жагсаалтад нэмнэ. 2. pr доторх анхны тоо p бүрийн хувьд lp[i × p] = p гэж бичнэ. 3. p > lp[i] эсвэл i × p > n болмогц зогсоно. 4. Ингэснээр нийлмэл тоо бүр өөрийн хамгийн бага анхны хуваагчаар нэг л удаа зурагдана. Оролт: n. Анхны тоонуудыг хэвлэнэ.

Яагаад зөв, хэр хурдан бэ?

Нийлмэл x-ийн хамгийн бага анхны хуваагчийг p гэе. x = i × p бол i-н бүх анхны хуваагч p-гээс багагүй, тиймээс p ≤ lp[i]. Тэгэхээр i дээр ирэхэд x заавал зурагдана. Өөр p' хуваагчаар x-ийг зурах гэвэл p' > lp[i'] нөхцөл зөрчигдөнө. Иймд тоо бүр яг нэг удаа зурагдана.

Нийт зурах үйлдлийн тоо нь нийлмэл тоонуудын тоотой тэнцүү, тиймээс O(n). n = 10⁷ бол 10 сая орчим үйлдэл. Санах ой: lp array n + 1 хэмжээтэй.

Түгээмэл алдаа

  • pr[j] <= lp[i] нөхцөлийг мартах. Тэгвэл тоо олон удаа зурагдаж, lp буруу утгатай болно.
  • i * pr[j] int-ээс хэтрэх. n ойролцоогоор 10⁷ бол асуудалгүй, гэхдээ шалгалтыг i * pr[j] <= n гэж үржвэрээр хийдэг тул n том бол long long хэрэглэ.
  • lp array-г n-ээс бага зарлах. Index n хүртэл хэрэгтэй тул n + 1.

Хязгаарын тохиолдол

  • n = 2: ганц анхны тоо 2 олдоно, зурах тоо алга.
  • Анхны тоо i дээр: lp[i] = i тул pr доторх бүх анхны тоогоор (n-ээс хэтрэхгүй бол) үржүүлнэ.
  • n = 30-аас 60 болгоход шинэ анхны тоонууд нэмэгдэх ч өмнөх lp утгууд өөрчлөгдөхгүй.

Өөрийгөө шалга

  1. lp[45] хэд вэ? 45-ыг аль i үед зурах вэ?

    Хариу харах

    lp[45] = 3. i = 15 үед 15 × 3 гэж зурна, учир нь lp[15] = 3.

  2. n = 30 бол нийт хэдэн удаа зурах вэ?

    Хариу харах

    19. 2-оос 30 хүртэл 29 тоо, үүнээс 10 нь анхны, 19 нь нийлмэл.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.n = 20 бол 2-оос 20 хүртэлх нийлмэл тоо бүрийн lp утгыг бич.

    Hint харах

    Зөвхөн 9 ба 15-ын lp нь 2 биш.

    Хариу ба тайлбар

    4, 6, 8, 10, 12, 14, 16, 18, 20-т 2. 9 ба 15-д 3.

  2. 2.lp array ашиглан дурын x ≤ n-ийг анхны үржвэрт задалдаг код бич.

    Hint харах

    lp[x] нь үргэлж анхны хуваагч.

    Хариу ба тайлбар

    while (x > 1) { cout << lp[x] << " "; x /= lp[x]; } Алхмын тоо нь хүчин зүйлсийн тоо, O(log x). 360 дээр 2 2 2 3 3 5.

  3. 3.Linear Sieve-ийн зэрэгцээ 1-ээс n хүртэлх бүх тооны φ-г ол.

    Hint харах

    p = lp[i] үед φ(i × p) = φ(i) × p. Бусад үед φ(i × p) = φ(i) × (p − 1).

    Хариу ба тайлбар

    Анхны i-д phi[i] = i - 1. Зурах бүрт дээрх хоёр томьёоны аль тохирохыг нь хэрэглэнэ. Нийт O(n) хэвээр.

Жишээ

Оролт

30

Гаралт

2 3 5 7 11 13 17 19 23 29