Тоог p = 2, 3, 4, … бүрт хуваагдахаа болитол хувааж, анхны тоонуудын үржвэрт задалдаг арга.

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

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

n = 84-ийг задалъя. p = 2: 84 → 42 → 21, хоёр удаа хуваагдлаа. p = 3: 21 → 7. p = 4 болоход 4 × 4 = 16 > 7 тул loop дуусна.

Үлдсэн 7 > 1 тул энэ нь бас анхны хүчин зүйл. Хариу: 84 = 2² × 3 × 7.

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

Энгийн арга бол 2-оос n хүртэл бүх тоогоор хувааж үзэх. n анхны бол n алхам, n = 10⁹ бол удаан.

Хэрэв n нийлмэл бол √n-ээс хэтрэхгүй хуваагчтай. Тиймээс p × p ≤ n хүртэл л хуваана. n-ийг хуваах бүрт багасгадаг тул loop улам эрт дуусна. Төгсгөлд нь n > 1 үлдвэл тэр нь анхны тоо.

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

p
Туршиж буй хуваагч. 2, 3, 4, … гэж нэмэгдэнэ.
n
Одоо хүртэл задраагүй үлдсэн хэсэг. Хуваах бүрт багасна.
анхны хүчин зүйл
Үржвэрт орсон анхны тоо. 300-д 2, 2, 3, 5, 5.
pn
300
n = 300
хүчин зүйлс
хоосон

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

Алхам 1 / 6
Хурд
  • Сая хуваасан
  • Одоогийн n
  • Олдсон хүчин зүйл
  • Хариу
Слайд 1 / 6

Анхны үржвэрт задлах

Тоо бүрийг анхны тоонуудын үржвэрээр ганцхан янзаар бичиж болно. 300-г задалъя. Хүснэгт нь сургуульд зурдаг «шат» шиг.

prime-factorization.cpp
#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
cin >> n;
for (int p = 2; p * p <= n; p++) {
for (; n % p == 0; n /= p) cout << p << ' ';
}
if (n > 1) {
cout << n;
}
cout << '\n';
return 0;
}

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

Тоог анхны хүчин зүйлсээр нь бичнэ: 300 = 2² × 3 × 5². GCD, LCM, хуваагчдын тоо, φ(n) олох олон бодлогын эхний алхам.

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

1. p = 2-оос эхлэн p × p ≤ n байх хооронд давтана. 2. n нь p-д хуваагдаж байвал p-г хэвлээд n /= p. Хуваагдахаа болитол давтана. 3. n багасах тусам давталт эрт зогсоно. 4. Эцэст нь n > 1 үлдсэн бол тэр нь анхны тоо. Түүнийг бас хэвлэнэ. Нийлмэл p хэзээ ч хуваахгүй: түүний анхны хуваагчдаар аль хэдийн бүрэн хуваачихсан байдаг. Оролт: n. Анхны хүчин зүйлсийг өсөх дарааллаар хэвлэнэ.

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

p-д хуваагдахаа болитол хуваадаг тул p-гээс бага анхны хуваагч n-д үлдэхгүй. Иймээс p нийлмэл байхад n-ийг хуваах боломжгүй, хэвлэгдсэн p бүр анхны. Loop p × p > n болоход зогсоно. Энэ үед n-ий √n-ээс бага хуваагч байхгүй тул n нь 1 эсвэл анхны тоо.

Хамгийн муудаа √n алхам: n = 10⁹ бол 31 623 орчим. Хуваалт бүр n-ийг ядаж хоёр дахин багасгадаг тул хуваах үйлдэл log₂ n-ээс хэтрэхгүй.

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

  • Loop-ын дараах if (n > 1) хэсгийг мартах. 84 дээр 7 хэвлэгдэхгүй.
  • p * p <= n дээр int хэтрэх. n нь 10¹² орчим бол long long p.
  • if ашиглаж ганц удаа хуваах. 84 дээр 2-ыг ганц л удаа олно. Хуваагдахаа болитол while-аар хуваа.

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

  • n анхны тоо: loop-д нэг ч хуваагч олдохгүй, төгсгөлд n өөрийг нь хэвлэнэ.
  • n нь 2-ын зэрэг, жишээ нь 1024: p = 2 дээр 10 удаа хуваагдаж n = 1 болно.
  • n = 1: loop ажиллахгүй, юу ч хэвлэхгүй. Бодлогын шаардлагыг шалга.

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

  1. 97-г задлахад хэдэн p шалгах вэ?

    Хариу харах

    8. p = 2 … 9, учир нь 9 × 9 = 81 ≤ 97 < 100. Нэг ч хуваагч олдохгүй тул 97 анхны.

  2. 1024-ийг задлахад юу хэвлэх вэ?

    Хариу харах

    2-ыг 10 удаа. 1024 = 2¹⁰.

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

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

  1. 1.360-ыг гараар задал.

    Hint харах

    Эхлээд 2-т хуваагдахаа болитол хуваа.

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

    360 → 180 → 90 → 45 (2³), 45 → 15 → 5 (3²), үлдсэн 5. 360 = 2³ × 3² × 5.

  2. 2.Хариуг 2^3 3^2 5^1 хэлбэрээр, зэргийг нь хамт хэвлэдэг болго.

    Hint харах

    p бүрт хэдэн удаа хуваагдсаныг тоол.

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

    p бүрт int k = 0; while (n % p == 0) { n /= p; k++; }, k > 0 бол p^k-г хэвлэнэ. Төгсгөлд n > 1 бол n^1.

  3. 3.Задаргаа ашиглан хуваагчдын тоог ол. 360 хэдэн хуваагчтай вэ?

    Hint харах

    p^k бүр хуваагчид 0-ээс k хүртэлх зэргээр ордог.

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

    (3 + 1)(2 + 1)(1 + 1) = 24. Ерөнхийдөө зэрэг бүр дээр нэгийг нэмээд үржүүлнэ.

Жишээ

Оролт

300

Гаралт

2 2 3 5 5

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

Бодлого

Хичээл

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