Editorial for Bedao Regular Contest 03 - PRIME


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

Thuật toán trâu

Với mỗi số ~n~ từ ~a~ đến ~b~, ta xét tất cả các ước của ~n~ rồi kiểm tra số đó có phải nguyên tố hay không.

Thuật toán tối ưu hơn:

Một số ~n~ có ~k~ ước nguyên tố khác nhau đồng nghĩa với trong cách phân tích thừa số nguyên tố của ~n~, có đủ ~k~ thừa số nguyên tố. Ví dụ ~20~ có ~2~ ước thừa số nguyên tố khác nhau ~(20 = 2 \times 2 \times 5, 2~ ước nguyên tố là ~2~ và ~5)~.

Đến đây thì ta sử dụng sàng nguyên tố để phân tích thừa số nguyên tố, sử dụng kĩ thuật Prefix Sum để trả lời mỗi truy vấn trong ~O(1)~ với đoạn ~[L,R]~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.