Hôm trước có bác nào đó bên ĐH GTVT HN gửi mail nhờ em viết giúp chương trình nhập vào một số N, và xuất ra các ước số nguyên tố của nó, giờ mới nhớ lại.

Bài này cơ bản không khó nhưng em vẫn chưa tìm được thuật toán tối ưu. Để em trình bày với các bác thuật toán tốt nhất em đã tìm được nhé:

Trích dẫn:

Bước 1: cho i chạy từ 2 ---> sqrt(N) và kiểm tra N có chia hết cho i. Nếu chia hết, lưu i vào một mảng A và chia N cho i. Sau đó lặp lại bước 2 này. Bước 2: đến lúc này thì số N còn lại chắc chắn là số nguyên tố --> lưu N vào mảng A // mục đích 2 bước này là tìm tất cả ước số của N Bước 3: kiểm tra toàn bộ mảng A, nếu có phần tử nào là số nguyên tố thì xuất kết quả ra màn hình.

Lúc đầu, em làm theo kiểu cho i chạy từ 1 --> sqrt(N), sau đó kiểm tra i có phải là số NT, nếu i là số NT thì mới kiểm tra N có chia hết cho i không ---> công nhận cách này ngu thật!

Tuy nhiên thuật toán trên em vẫn thấy chưa ổn. Vì nếu nhập vào một số lớn (bằng tích của nhiều số NT lớn) ví dụ như số 16448819582037859 (là tích 2 số NT là 379721, 43318171979) sẽ chạy rất lâu

Ai có cách nào không?


---------------------

Àh, dĩ nhiên phải có thêm 1 bước là kiểm tra i đã có trong mảng A chưa, nếu chưa mới thêm i vào A nhé. Tuy nhiên việc này không giải quyết được nhiều lắm.