n-ийг 2, 3, 4, … тоонуудад хувааж үзээд анхны эсэхийг шалгадаг энгийн арга. d × d > n болмогц зогсоно.

Basic LevelХугацаа: O(√n)Санах ой: O(1)
HackerRank дээр бодох

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

91 анхны тоо юу? d = 2, 3, 4, 5, 6 гэж хуваахад бүгд үлдэгдэлтэй. d = 7 үед 91 = 7 · 13, үлдэгдэлгүй хуваагдлаа. Тэгэхээр 91 анхны биш, хариу NO.

Харин 97-г шалгахад d = 2 … 9 хүртэл нэг ч хуваагч олдохгүй. d = 10 үед 10 · 10 > 97 тул зогсоно. 97 анхны тоо, хариу YES.

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

Тодорхойлолтоор нь бол 2-оос n − 1 хүртэлх бүх тоонд хувааж үзнэ. n = 10⁹ бол тэрбум хуваалт, хэт удаан.

Гэтэл n = d · q гэж задарвал d, q хоёрын бага нь √n-ээс их байж чадахгүй. Тиймээс d * d <= n хүртэл л шалгахад хангалттай. Тэр хооронд хуваагч олдохгүй бол n анхны тоо.

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

анхны тоо
Зөвхөн 1 ба өөртөө хуваагддаг, 2-оос багагүй тоо.
d
Туршиж буй хуваагч. 2-оос эхэлнэ.
d * d <= n
Loop-ын нөхцөл. sqrt() ашигладаггүй тул бутархайн алдаа гарахгүй.
prime
Хариу. Эхэндээ n >= 2 эсэх, хуваагч олдвол false.
2
3
4
5
6
7
8
9
10
n = 97

97 анхны тоо юу? Анхны тоо зөвхөн 1 ба өөртөө хуваагддаг. d = 2, 3, 4, … гэж хувааж үзье. d × d > 97 болмогц зогсоно.

Алхам 1 / 10
Хурд
  • Шалгаж буй d
  • Хуваагч биш
  • Хуваагч
  • d × d > n: шалгахгүй
Слайд 1 / 6

Анхны тоо

2, 3, 5, 7, 11 гэх мэт тоо зөвхөн 1 ба өөртөө хуваагддаг. Ийм тоог анхны тоо гэдэг. 97 анхны тоо юу?

prime-check.cpp
#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
cin >> n;
bool prime = (n >= 2);
for (int d = 2; d * d <= n; d++) {
if (n % d == 0) {
prime = false;
break;
}
}
cout << (prime ? "YES" : "NO") << '\n';
return 0;
}

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

Нэг тоо анхны эсэхийг мэдэх. Хуваагчийг n хүртэл биш, √n хүртэл л хайдаг тул тэрбум орчим тоог ч хурдан шалгана.

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

1. Анхны тоо хамгийн багадаа 2 байдаг: n < 2 бол анхны биш. 2. d = 2, 3, 4, … гэж d × d ≤ n байх хооронд давтана. 3. n % d = 0 бол хуваагч олдлоо: анхны биш, давталтаас гарна. 4. Хуваагч олдоогүй бол n анхны тоо. Яагаад d × d ≤ n хүртэл вэ? n = d × q гэж задарвал d, q хоёрын бага нь үргэлж d × d ≤ n нөхцөлийг хангана. Оролт: n. Анхны бол YES, үгүй бол NO хэвлэнэ.

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

n нийлмэл тоо бол түүний хамгийн бага хуваагч d нь d · d ≤ n нөхцөлийг заавал хангана. Тиймээс loop түүнийг заавал олно. Хуваагч олдоогүй бол n анхны.

Хамгийн ихдээ √n орчим хуваалт: хугацаа O(√n). n = 10⁹ + 7 бол 31 621 хуваалт, маш хурдан. Гэхдээ 10⁵ тоо тус бүрийг шалгах бол Sieve of Eratosthenes илүү тохиромжтой.

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

  • 1-ийг анхны гэж үзэх. 1 анхны тоо биш, код prime = (n >= 2) гэж эхэлдэг.
  • n нь 2 · 10⁹ орчим үед d * d int-ээс хэтэрнэ. long long ашигла.
  • d * d < n гэж бичвэл анхны тооны квадратыг (49, 121) анхны гэж буруу хэлнэ.
  • Нөхцөлийг d < n гэж бичвэл зөв ажиллах ч хэт удаан.

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

  • n = 1: loop ажиллахгүй, prime = false, хариу NO.
  • n = 2, 3: 2 · 2 > n тул loop ажиллахгүй, хариу YES.
  • n = 4: d = 2 дээр шууд олдоно.
  • Анхны тооны квадрат (49 = 7 · 7): d = 7 хүртэл шалгах ёстой. <= яагаад хэрэгтэйг энд л харна.

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

  1. n = 97 бол хэдэн удаа хуваах вэ?

    Хариу харах

    8: d = 2, 3, …, 9. d = 10 үед 100 > 97 тул зогсоно.

  2. n = 121 анхны тоо юу?

    Хариу харах

    Үгүй. 121 = 11 · 11, d = 11 дээр олдоно.

  3. n = 10⁹ + 7 анхны тоо. Хэдэн удаа хуваах вэ?

    Хариу харах

    31 621: d = 2-оос 31 622 хүртэл.

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

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

  1. 1.n = 221 анхны тоо юу? Хэдэн удаа хуваах вэ?

    Hint харах

    d · d ≤ 221 гэдэг нь d ≤ 14.

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

    Анхны биш: 221 = 13 · 17. d = 2-оос 13 хүртэл 12 удаа хуваана.

  2. 2.n-ий 1-ээс өөр хамгийн бага хуваагчийг хэвлэдэг болго.

    Hint харах

    Анхны тоо бол хамгийн бага хуваагч нь өөрөө.

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

    Хуваагч олдвол d-г хэвлээд дуусгана. Loop дуусахад олдоогүй бол n-ийг хэвлэнэ (n ≥ 2).

  3. 3.n-ийг анхны тоонуудын үржвэрт задал (n ≤ 10⁹). Жишээ нь 360 = 2³ · 3² · 5.

    Hint харах

    d-д хуваагдахаа болитол хуваа. Loop дуусахад n > 1 үлдвэл тэр юу вэ?

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

    for (d = 2; d * d <= n; d++) while (n % d == 0) { cout << d << ' '; n /= d; }. Эцэст нь n > 1 бол тэр нь бас анхны хуваагч. O(√n).

Жишээ

Оролт

97

Гаралт

YES

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

Бодлого

Хичээл

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