Hướng dẫn giải của Số ước nguyên tố
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Đề hỏi trong các ước của ~n~ (~2 \le n \le 10^{12}~) có bao nhiêu ước là số nguyên tố. Ước nguyên tố của ~n~ chính là các thừa số nguyên tố phân biệt của ~n~, nên đáp số là số thừa số nguyên tố phân biệt của ~n~.
Sub 1: Vét cạn — ~O(n \sqrt{n})~, dùng khi ~n \le 1000~
Thử từng số ~d~ từ 2 đến ~n~: nếu ~d~ chia hết ~n~ và ~d~ là số nguyên tố (thử chia) thì đếm. Nếu chỉ nộp sub này: đúng 20/24 test.
Sub 2: Liệt kê ước — ~O(n)~, dùng khi ~n \le 10^6~
Chỉ thử ~d \le \sqrt{n}~; mỗi ~d~ cho hai ước là ~d~ và ~n/d~, kiểm tra từng ước có nguyên tố không. Chạy riêng sub này: đúng 24/24 test.
Sub 3: Phân tích thừa số — ~O(\sqrt{n})~, dùng khi ~n \le 10^{12}~
Phân tích ~n~ thành thừa số nguyên tố bằng thử chia đến ~\sqrt{n}~ (không quá ~10^6~ lần lặp). Mỗi thừa số nguyên tố chỉ đếm một lần dù có mũ bao nhiêu. Chạy riêng sub này: đúng 24/24 test.
Chương trình hoàn chỉnh
Chương trình đọc ~n~, nếu ~n \le 1000~ gọi sub1, nếu ~n \le 10^6~ gọi sub2, còn lại gọi sub3. Sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
Số test: 24 (chương trình đầy đủ đúng 24/24).
#include <bits/stdc++.h>
using namespace std;
long long n;
// Kiem tra v (v >= 2) co phai so nguyen to khong (thu chia tu 2 den sqrt(v))
bool isPrimeTD(long long v) {
if (v < 2) return false;
for (long long d = 2; d * d <= v; d++)
if (v % d == 0) return false;
return true;
}
// Sub 1: vet can. Thu tung d tu 2 den n: neu d la uoc cua n va d la so nguyen to thi dem
// Dung khi n <= 1000
void sub1() {
long long cnt = 0;
for (long long d = 2; d <= n; d++)
if (n % d == 0 && isPrimeTD(d)) cnt++;
cout << cnt << "\n";
}
// Sub 2: liet ke uoc cua n bang cach thu d <= sqrt(n) (moi d cho ra 2 uoc d va n/d),
// uoc nao la so nguyen to thi dem (dung set de khong dem trung khi d = n/d)
// Dung khi n <= 10^6
void sub2() {
set<long long> primeDivs;
for (long long d = 1; d * d <= n; d++) {
if (n % d != 0) continue;
if (isPrimeTD(d)) primeDivs.insert(d);
long long e = n / d;
if (isPrimeTD(e)) primeDivs.insert(e);
}
cout << primeDivs.size() << "\n";
}
// Sub 3: day du. Uoc nguyen to cua n chinh la cac thua so nguyen to phan biet cua n.
// Phan tich n bang thu chia den sqrt(n) (<= 10^6 lan lap), dem so thua so nguyen to phan biet.
void sub3() {
long long m = n, cnt = 0;
for (long long p = 2; p * p <= m; p++) {
if (m % p == 0) {
cnt++;
while (m % p == 0) m /= p; // bo het luy thua cua p
}
}
if (m > 1) cnt++; // phan con lai la mot so nguyen to lon
cout << cnt << "\n";
}
int main() {
freopen("UocNT.inp", "r", stdin);
freopen("UocNT.out", "w", stdout);
cin >> n;
if (n <= 1000) sub1();
else if (n <= 1000000) sub2();
else sub3();
return 0;
}
Bình luận