Phân tích một số ra các thừa số nguyên tố ?

[Master_Baby]

- Gửi thanh1234:

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 !

Hay nhỉ, đã là số nguyên tố mà còn giả sử chia hết cho m.:??:
Cách làm này cũng không ổn, bạn lấy đâu ra m? Chả lẽ lại for? for vậy chắc là for từ 2? Và nếu số đó chia hết cho 2 thì chả lẽ lại lấy 2 làm chuẩn luôn? Giả sử ngược lại, For từ n downto thì còn lâu hơn cách bình thường (là cách tìm số nguyên tố).
Theo "ngộ", khi đã tìm được một số nguyên tố m nào đó sao cho n mod m =0 thì:

repeat
n:=round(n/m); 
until n MOD m <> 0

{mặc dù n/m là nguyên nhưng vẫn phải dùng round vì pascal không cho phép gán biến integer cho 1 phép chia, nếu n là real thì không thể sử dụng MOD}

(có gì sai sót xin chỉ rõ, cảm ơn trước!)
- Master baby

[grenadier1991]

Sorry các bác, em thấy bác F12 sai chớ. Nếu số đó là số nguyên tố thì sao?

[F12]

Sorry các bác, em thấy bác F12 sai chớ. Nếu số đó là số nguyên tố thì sao?

Nếu một số nguyên x không chia hết cho các số nguyên tố từ 2 đến sqrt(x) thì chẳng phải bác có thể kết luận ngay nó là số nguyên tố, và ghi nó ra kết quả còn gì ạ.

Em không sai đâu nhé.

[thanh1234]

À quên thay phép chia(/)ta dùng phép div ,đúng như bác Baby nói thì nếu chia hết cho 2 thì lấy 2 làm chuẩn luôn ,ta dùng vòng for cho việc này ,nếu gặp m vừa ý thì thoát khỏi for luôn(nhớ nhé)và làm lại!
Việc chia liên tục lặp lại các số nhỏ từ 2 ta luôn đảm bảo m là nguyên tố!

Mà thôi không cần dùng vòng for nữa ,tôi dùng 2 vòng while lồng nhau ,kết quả là mỹ mãn!

[Master_Baby]

- Gửi thanh1234:
Thực ra đây là một bài toán khá cơ bản. Việc cần làm bây giờ là cải tiến nó. Sao cho tối ưu nhất. Ngộ xin đưa một ví dụ:
Giờ ta cải tiến cách làm để tìm số nguyên tố. Chuẩn bị sẵn một mảng để lưu, giả sử mảng P. Gán luôn vị trí P[1]=2. Sau đó, dò như vầy:

i:=1;
t:=2;
repeat
 i:=i+2;
 if ngto(i)=true then 
  begin
    P[t]:=i;
    t:=t+1;
  end;
until i>trunc(sqrt(n))

function ngto thì viết như vầy:
- Việc thử 1 số là số nguyên tố không nhất thiết là phải ko chia hết cho 1(hay nhiều) trong các số từ 2 đến sqrt.
- Thay vì thử quá nhiều như vầy, chi bằng ta thử số đó có chia hết cho các số nguyên tố đứng trước nó ko? Để nhanh hơn, ta có thể giới hạn các số nguyên tố để thử chia hết trong khoảng 2 đến sqrt.

(có gì sai sót xin chỉ giáo, cám ơn trước!)
- Master_Baby

[tungnhoi]

"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

Bác cũng sai rùi bác thử phân tích số 21 đi xem nào
21 = 3*7 thế số 7 có lớn hơn sqrt(21) ko (sqrt(21) xấp xỉ 4)

em nghĩ ít nhất phải cho chạy từ 2 cho đến n div 2 ko thì cái trường hợp 21 sẽ ko tách đc.

[bete]

bác thử phân tích số 21 đi xem nào
21 = 3*7 thế số 7 có lớn hơn sqrt(21) ko (sqrt(21) xấp xỉ 4)

Cám ơn bạn tungnhoi đã góp ý.

Nếu a = b*c thì mình phải có b hoặc c lớn hơn hay bằng căn bậc 2 của a (vì nếu cả b lẫn c đều nhỏ hơn căn bậc 2 của a thì b*c nhỏ hơn căn bậc 2 của a => mình không thể nào có a = b*c)

Trở lại ví dụ của bạn:
N=21: thử các số nguyên tố nhỏ hơn căn bậc 2 của N => thử 2 và 3 => N chia hết cho 3 => N=3*7 với 3 là một số nguyên tố nhỏ hơn hay bằng căn bậc 2 của N
Thay N bằng N/3 => N=7 (3 đã là một số nguyên tố rồi nên mình chỉ cần lo phần còn lại là 7)
N=7: thử các số nguyên tố nhỏ hơn căn bậc 2 của N => thử 2 => N không chia hết cho 2 => 7 là một số nguyên tố
=> 3*7 là cách phân tích 21 ra các thừa số nguyên tố

Một ví dụ khác:
N=8: thử các số nguyên tố nhỏ hơn căn bậc 2 của N => thử 2 => N chia hết cho 2 => N=2*4 với 2 là một số nguyên tố nhỏ hơn hay bằng căn bậc 2 của N
Thay N bằng N/2 => N=4 (2 đã là một số nguyên tố rồi nên mình chỉ cần lo phần còn lại là 4)
N=4: thử các số nguyên tố nhỏ hơn căn bậc 2 của N => thử 2 => N chia hết cho 2 => N=2*2 với 2 là một số nguyên tố nhỏ hơn hay bằng căn bậc 2 của N
Thay N bằng N/2 => N=2 (2 đã là một số nguyên tố rồi nên mình chỉ cần lo phần còn lại là 2)
N=2: thử các số nguyên tố nhỏ hơn căn bậc 2 của N => không có số nào hết => N=2 là một số nguyên tố (cũng có thể dừng ngay ở bước trên: khi có N=a*a với a là 1 số nguyên tố)
=> 2*2*2 là cách phân tích 8 ra các thừa số nguyên tố

Nếu mình thử các số nguyên tố theo thứ tự từ nhỏ tới lớn:
Nếu N=a*b (với a là một số nguyên tố) thì bước kế khi mình thay N bằng b: chỉ cần thử các số nguyên tố lớn hơn hay bằng a (thay vì thử lại bắt đầu từ 2) và nhỏ hơn hay bằng căn bậc 2 của N

(có gì sai sót mong được góp ý, xin cám ơn)

-thân

[xbach17]

uses crt;
var n,i,j,dem,mu:longint;
begin
clrscr;
write('nhap n:');readln(n);
write(n,'=');
for i:=2 to n-1 do
begin
if (n mod i=0) then
begin
for j:=2 to i do
begin
if i mod j=0 then break;
end;
if j=i then
begin
dem:=0;mu:=1;
repeat
mu:=mu*i;
dem:=dem+1;
until n mod mu<>0;
write(i,'^',dem-1,'*');
end;
end;
end;
readln;
end.
BÀi giải đây!

[xbach17]

Cách này tuy hơi dài nhưng khỏi phải suy nghĩ nhiều!!!

[thuonghcm]

var i,n:integer;
begin
n:=6;
repeat
i:=2;
while (n mod i<>0)and(i<n) do inc(i);
write(i:5);
n:=n div i;
until n=1;
end.