Cho hỏi tên cty với
) bài này code 20 phút khá căng đó.
Cách giải tốt nhất là tạo mảng chứa số nguyên tố rồi tính độ dài của từng thằng từ 2 tới sqrt(n), rồi suy ra vị trí cần tìm là bội số mấy, sau đó lấy thứ tự nhân ngược lại ước số nguyên tố kia là ra. Mấy cái công thức để tính thì khó ở chỗ phải loại trừ những thằng chia hết cho nhiều số.
- ví dụ n=1000000 thì 500000 thằng đầu tiên là bội của 2 (n div 2), tầm 300000 thằng tiếp theo là bội của 3 (n div 3 - n div 6), 100000 thằng tiếp theo là bội của 5 (n div 5 - n div 10 - n div 15 + n div 30)
Phần tricky của bài này là làm cách nào có đc mảng số nguyên tố 1 cách nhanh nhất. Cách làm tốt nhất là google rồi hardcode 1 mảng số nguyên tố từ 2 tới 1000. Mảng này tầm 200 số chứ ko nhiều.
độ phức tạp là tầm 200 lần lặp và phép toán div, chạy tầm 100ms là căng.