Kiến thức

Đếm số ước nguyên tố của một số – Nhan Nguyen – Software Engineer

Bạn đang xem: Đếm số ước nguyên tố của một số – Nhan Nguyen – Software Engineer

Đếm số ước nguyên tố của một số

2017-07-28

  • algorithm


Bài gốc

Codeforces 546D

Đề bài

Cho q truy vấn là q số nguyên n, cho biết số ước nguyên tố của n.

Giới hạn:

  • 1 ≤ q ≤ 1e6
  • 1 ≤ n ≤ 1e6
Định dạng test

Input:

  • Dòng đầu là q.
  • q dòng tiếp theo, mỗi dòng là một số n.

Output:

  • q dòng trả lời cho q truy vấn: số ước nguyên tố của n.

Ví dụ:

input: 5 1 11 45 10000 output: 0 1 3 8
Thuật toán

Định dạng

sàng Eratosthenes

: gọi primeFactor[n] là số ước nguyên tố của n, với mỗi số nguyên tố a, tính primeFactor[] cho các bội b của a như sau:

primeFactor[b] = primeFactor[b/a] + 1

Source code

Ngôn ngữ: C++.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 
const ll N = 1e6 + 5; int q, primeFactor[N]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); for(ll i = 2; i < N; i++) if (primeFactor[i] == 0) for(ll j = i; j < N; j += i) primeFactor[j] = primeFactor[j/i] + 1; cin >> q; while(q--) { int n; cin >> n; cout << primeFactor[n] << 'n'; } return 0; }

Độ phức tạp

Độ phức tạp của đoạn sàng: xấp xỉ O(NlogNlogN).

Độ phức tạp tổng quát: O(NlogNlogN + q)

Please enable JavaScript to view the

comments powered by Disqus.

Chuyên mục: Kiến thức

Related Articles

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *

Back to top button