Анхны тоо бүрийн үржвэрийг зурж хассаар n хүртэлх бүх анхны тоог нэг дор олдог арга.

Pre-IntermediateХугацаа: O(n log log n)Санах ой: O(n)
HackerRank дээр бодох

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

20 хүртэлх анхны тоонуудыг олъё. 2-ын үржвэр 4, 6, 8, …, 20-ийг зурна. Дараа нь 3-ын үржвэр 9, 12, 15, 18-ыг зурна.

5 · 5 = 25 > 20 тул цааш зурах хэрэггүй. Зурагдаагүй үлдсэн нь 2 3 5 7 11 13 17 19: нийт 8 анхны тоо.

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

n хүртэлх тоо бүрийг Prime Check-ээр шалгавал n √n орчим алхам. n = 10⁶ бол тэрбум орчим, удаан.

Эсрэгээр нь бодъё: анхны биш тоог "зурж" хаяна. 2 анхны тул 4, 6, 8, … зурагдана. Дараагийн зурагдаагүй тоо 3 бас анхны тул 9, 12, 15, … зурагдана. Зурагдаагүй үлдсэн тоо бүр анхны, учир нь өөрөөсөө бага ямар ч анхны тоонд хуваагдаагүй.

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

np
"not prime". np[x] = true бол x анхны биш. Global array тул эхэндээ бүгд false.
p
Шалгаж буй тоо. p * p <= n хүртэл явна.
p * p
Зурж эхлэх тоо. Үүнээс бага үржвэрүүд нь илүү бага анхны тоонд аль хэдийн зурагдсан.
m
Зурж буй үржвэр: p · p, p · p + p, p · p + 2p, …
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

50 хүртэлх анхны тоонуудыг олъё. 1 анхны тоо биш. Анхны тоо бүрийн үржвэрүүдийг зурж хасна. Үлдсэн нь анхны тоо.

Алхам 1 / 12
Хурд
  • Анхны p
  • Зурагдсан p
  • Сая зурсан
  • Анхны биш
  • Олдсон анхны тоо
  • Анхны тоо
Слайд 1 / 7

Шигшүүр

50 хүртэлх бүх анхны тоог олъё. Тоо бүрийг тусад нь шалгахын оронд анхны тоо бүрийн үржвэрийг зурж хасна. Үлдсэн нь анхны тоо.

sieve-eratosthenes.cpp
#include <bits/stdc++.h>
using namespace std;
int n;
bool np[1000005];
int main() {
cin >> n;
for (int p = 2; p * p <= n; p++) {
if (!np[p]) {
for (int m = p * p; m <= n; m += p) np[m] = true;
}
}
for (int i = 2; i <= n; i++) if (!np[i]) cout << i << ' ';
return 0;
}

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

n хүртэлх бүх анхны тоог олох. Олон тоо анхны эсэхийг асуудаг бодлогод тоо бүрийг тусад нь шалгахаас хамаагүй хурдан.

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

1. np[x] = true гэдэг нь «x анхны биш» гэсэн тэмдэг. Эхэндээ бүгд false. 2. p = 2, 3, … гэж p × p ≤ n байх хооронд давтана. 3. p зурагдаагүй (np[p] = false) бол анхны тоо. Түүний p × p, p × p + p, … үржвэрүүдийг зурна. 4. Эцэст нь зурагдаагүй үлдсэн 2 … n тоонууд бүгд анхны тоо. Оролт: n.

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

x нийлмэл тоо бол түүний хамгийн бага анхны хуваагч p нь p · p ≤ x нөхцөлийг хангана. Тэр p-гийн ээлж ирэхэд x зурагдана. Анхны тоо өөрөөсөө бага анхны тоонд хуваагдахгүй тул хэзээ ч зурагдахгүй.

Зурах үйлдлийн нийт тоо n/2 + n/3 + n/5 + … нь O(n log log n), бараг шугаман. n = 10⁶ бол 2 сая орчим зурах үйлдэл. Санах ой O(n).

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

  • np-г main дотор зарлавал эхний утга нь 0 биш, хог утга байж болно. Global зарла, эсвэл бүгдийг false болго.
  • Гадна loop-ыг p <= n хүртэл гүйлгэвэл p том үед p * p int-ээс хэтэрч, array-гээс гадуур бичнэ. p * p <= n хангалттай.
  • 0 ба 1-ийг анхны гэж хэвлэх. Хэвлэх loop i = 2-оос эхэлдэг.
  • n = 10⁸ бол bool np[] 100 MB болно. Санах ойн хязгаарыг шалга.

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

  • n = 2, 3: гадна loop ажиллахгүй, зөвхөн хэвлэнэ.
  • n = 4: p = 2 дээр 4 зурагдана, хариу 2 3.
  • n нь анхны тооны квадрат (49): p = 7 үед 49 зурагдана. Нөхцөлд <= чухал.

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

  1. n = 50 бол хэдэн анхны тоо гарах вэ?

    Хариу харах

    15.

  2. p = 5 үед хамгийн түрүүнд аль тоог зурах вэ?

    Хариу харах

    25. 10, 15, 20 нь 2-ын эсвэл 3-ын үржвэр тул аль хэдийн зурагдсан.

  3. n = 100 бол p хамгийн ихдээ хэд хүртэл шалгагдах вэ?

    Хариу харах

    10. 10 · 10 = 100 ≤ 100, харин 11 · 11 > 100.

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

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

  1. 1.n = 30 үед аль p-д зурах ажил хийгдэх вэ? Хариуг бич.

    Hint харах

    p · p ≤ 30 гэдэг нь p ≤ 5.

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

    p = 2, 3, 5 үед зурна. p = 4 аль хэдийн зурагдсан тул алгасна. Хариу: 2 3 5 7 11 13 17 19 23 29.

  2. 2.n хүртэл хэдэн анхны тоо байгааг л хэвлэдэг болго.

    Hint харах

    Зөвхөн хэвлэх мөрийг өөрчил.

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

    int cnt = 0; for (int i = 2; i <= n; i++) if (!np[i]) cnt++; дараа нь cnt утгыг хэвлэнэ. n = 1 000 000 бол 78 498.

  3. 3.n хүртэлх тоо бүрийн хамгийн бага анхны хуваагчийг spf[x]-д хадгал. Дараа нь дурын x ≤ n-ийг хурдан задал.

    Hint харах

    Зурах үедээ "чамайг аль p зурсан бэ?" гэдгийг хадгал.

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

    Зурахдаа if (spf[m] == 0) spf[m] = p;. Зурагдаагүй тоонд spf[x] = x. Задлахдаа x > 1 хооронд spf[x]-г хэвлээд x /= spf[x]. Нэг задаргаа O(log x).

Жишээ

Оролт

50

Гаралт

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.