30/09/2018, 17:09
Hỏi về thuật toán phân tích một số ra thừa số nguyên tố
Em đang học Pascal. Đang làm bài về phân tích một số ra thừa số nguyên tố. Code của nó trong Pascal thế này
i:=2;
repeat
while (n mod i <> 0) do
i:=i+1;
write(i);
n:=n div i;
if n > 1 then write ('*');
until n = 1;
em không hiểu tại sao lại thế. các bác giảng cho em được không ạ
Bài liên quan
Theo mình hiểu thì đây là chia lần lượt cho các số bát đầu từ 2, nếu chia hết thì xuất ra và thêm dấu nhân phía sau, rồi lại lấy thương để tiếp tục, cò không chia hết thì bỏ qua
thế tại sao nó lại tránh được các số không phải số nguyên tố hả bác
Bởi vì nếu nó chia hết cho hợp số. Tức là nó có thừa số nguyên tố nhỏ hơn, mà như vậy nó buộc phải bị phân tích từ trước rồi
Số không phải là số nguyên tố phân tích thành các số nguyên tố bé hơn nó rồi, ví dụ 12 chia hết cho 4 nhưng sau khi chia 2 lần cho 2 thì không chia hết cho 4
Cái này có thể sửa cận xuống sqrt(n).