Ai làm được bài lập trình :phân tích một số ra các thừa số nguyên tố cho tôi: giải thuật +chương trình ,thanks!
Ai làm được bài lập trình :phân tích một số ra các thừa số nguyên tố cho tôi: giải thuật +chương trình ,thanks!
Bạn thử làm theo cách bình thường xem. Lấy số đó chia cho các số nguyên tố từ 2 đến số đó. Nếu chia hết thì lấy thương đó chia tiếp, còn nếu không thì chia cho số nguyên tố tiếp theo. Cách này giống như khi phân tích ra thừa số nguyên tố trong toán học mà bạn thường làm ấy.
Cách này cho trường hợp đơn giản thôi chứ ,nếu số ta cần phân tích mà lớn và không may nó là số nguyên tố thì không được!
Làm như trên ta phải có một mảng lưu sẳn các số nguyên tố trước!
Thực sự chỉ cần lấy số đó chia cho các số nguyên tố từ 2 đên sqrt(số đó) thôi.
Bác thanh1234 yêu cầu số lớn đến thế nào vậy. Trong phạm vi longint thì thuật toán chạy nhanh lắm. Nhưng nếu ..vài trăm chữ số thì em.. bó tay.
Dòm kỹ lại bé ui! Hình như bé đọc sai đề. Thi rớt!Được gửi bởi F12
Em sai ở đâu vậy hả bác ? Chỉ cho em với, em xin hậu tạ :-SSĐược gửi bởi lee_huynh306
Người ta cần phân tích 1 số bất kỳ N ra thừa số nguyên tố với dạng N=a*b*c... (a,b,c: nguyên tố).
Trong khi đó bác biểu đi chia N cho 2 -> sqrt(N) <- check xem N là nguyên tố hay ko à?
Trong Forum này có khá nhiều bài giải vấn đề này, chịu khó search với từ "nguyên tố" là có ngay.
"lấy số đó chia cho các số nguyên từ 2 đên sqrt(số đó)" là 1 cách để kiểm tra coi 1 số có phải là số nguyên tố hay không
Còn "lấy số đó chia cho các số nguyên tố từ 2 đên sqrt(số đó)" là 1 cách đúng để phân tích ra thừa số nguyên tố
=> bạn F12 nói không có sai đâu
(chỉ khác nhau có 1 chữ "chia cho các số nguyên tố" và "chia cho các số nguyên" mà thôi)
-thân
Ta cải tiến lại cho nó hiệu quả hơn như sau:
giả sử số nguyên tố ta cần phân tích là n và nó chia hết cho m ,khi đó ta gán n:=n/m ; và ta chỉ cần làm lại tương tự với n mới này mà thôi !
Em không sai đâu nhé.
Điều này chỉ đúng với m nguyên tố thôi bạn ạ.Được gửi bởi thanh1234
Bookmarks