Đi tìm bội chung nhỏ nhất (3 số). BCNN của 3 số liên tiếp.

Hôm nay lên đồng, từ cái chương trình cơ bản phát triển lên thành chương trình tối ưu luôn (maybe) :D
Có một bạn, chia sẻ trên daynhauhoc một chương trình để tìm BCNN của 3 số.
Các bước tìm của bạn ấy như sau:

1. Tìm max của 3 số, ta gọi là GREATEST
2. Vào for cho i chạy từ GREATEST đến vô cùng, nếu i chia hết cho 3 số thì là số cần tìm. 

Lang thang vào, thấy hợp lý quá. Cơ mà, để ý, thằng GREATEST+1, GREATEST+2 cũng không chia hết cho GREATEST. Ít nhất thì nó cũng phải bằng 2 lần GREATEST thì mới chia hết cho GREATEST chứ. Thế là một cải tiến mới ra đời. (Cải tiến 1)

1. Tìm max của 3 số, ta gọi là GREATEST
2. Kiểm tra GREATEST có phải BCNN hay không.
3. Vào for cho i chạy từ GREATEST*2 đến vô cùng, nếu i chia hết cho 3 số thì là số cần tìm. 

Lại lên đồng, mình thấy thằng (GREATEST*2)+1 cũng đâu có chia hết cho GREATEST đâu. Thằng (GREATEST*3)+1 cũng không chia hết luôn. Rồi, cải tiến, again (Cải tiến 2)

1. Tìm max của 3 số, ta gọi là GREATEST
2. Vào for cho i chạy từ 1 đến vô cùng, nếu i*GREATEST chia hết cho 2 số thì là số cần tìm.

Lần cải tiến vừa rồi thì lời hơn nhiều, chỉ phải kiểm tra chia hết cho 2 số còn lại thôi. Các cải tiến trên đều dựa theo điều kiện cần "Nếu một số là BCNN của 3 số thì nó cũng là bội của mỗi số".

Vậy còn cải tiền nào nữa không?

Còn!!! Chúng ta có thể cải tiến thằng (Cải tiến 1) lên theo hướng khác. Nếu chúng ta biết các số còn lại có chứa các số nguyên tố nào mà GREATEST chưa có. Ta chỉ cần nhân vào và kiểm tra tịnh tiến cho i tăng dần. Có thể dễ thấy với trường hợp sau. 

a=10 b=6 c=18. GREATEST=18, tồn tại 3 snt là 2,3 và 5, 2 và 3 thì ở trong 18 rồi vậy thì . ta sẽ kiểm tra số 18*5.

Cách này thì dùng cho 3 số với khoảng cách lớn và số cũng phải bự nữa.

Vậy BCNN có gì phải chú ý nữa không. Với những cảm giác như ở những cải tiến trước, ta cảm thấy 3 số liên tiếp nhau sẽ có BCNN là tích của 3 số. Ồ, sau khi ngủ dậy mình lại có một cảm giác khác. nếu a là số chẵn thì BCNN bằng tích 3 số chia 2. nếu a lẻ thì bằng tích 3 số. Muốn biết rõ hay không thì phải chứng minh đã. Chứng minh = yên tâm.

Xét trường hợp a và c là số lẻ, b là số chẵn.
a=2k+1, b=2k+2, c=2k+3
tìm bội chung nhỏ nhất của 2 số a và c đã. Ta có BCNN=(a*c)/UCLN(a,c)
UCLN của a và c có thể tìm theo thuật toán Euler và UCLN của 2 số đó = 1.
Vậy BCNN của a và c là a*c.
Ta sẽ phải tìm BCNN của a*c và b. Tích a*c=4k^2+8k+3