Bài giảng Thuật toán: Phân tích một số thành tích các thừa số nguyên tố - Phan Đức Hoan

Chào mừng quý thầy cô và toàn thể các em 
TRƯỜNG CAO ĐĂNG SƯ PHẠM QUẢNG TRỊ 
KHOA CÔNG NGHỆ THÔNG TIN 
Giáo sinh: Phan Đức Hoan – Email: Hoante@yahoo.com 
Giáo sinh: Phan Đức Hoan 
KIỂM TRA BÀI CỦ 
Giáo sinh: Phan Đức Hoan 
-Bài toán: Phân tích một số thành tích các thừa số nguyên tố. 
- Ta xét ví dụ: 
	* 100 = 2 x 2 x 5 x 5 
	* 3003 = 3 x 7 x 11 x 13 
	* 7 = 7 
 vế trái là một số bất kì còn vế phải là các số nguyên tố. 
-Bài toán: Phân tích một số thành tích các thừa số nguyên tố. 
	+ Input: Số nguyên dương N. 
	+ Output: Dãy các số nguyên tố mà tích của nó chính bằng N. 
Ví dụ: 
	* 100 = 2 x 2 x 5 x 5 
	* 3003 = 3 x 7 x 11 x 13 
	* 7 = 7 
THUẬT TOÁN - PHÂN TÍCH MỘT SỐ THÀNH TÍCH CÁC THỪA SỐ NGUYÊN TỐ 
Em hãy nhắc lại Input và Output của bài toán trên ? 
Em hãy nhận xét các số ở vế trái và phải của phương trình ? 
Giáo sinh: Phan Đức Hoan 
Số nguyên tố là số chỉ chia hết cho 1 và chính nó. 
Vì khi N là số nguyên tố thì ngoài ước là 1 và chính nó ra không có ước nào nữa. 
Điều lưu ý thứ hai là số 1 không phải là số nguyên tố, củng không phải là hợp số. Lí do vì sao thì ta sẽ tìm hiểu ở phần sau. 
- Những điểm cần lưu ý: 
	+ Nếu N là số nguyên tố thì không cần phân tích nữa. 
	+ Số 1 không phải là số nguyên tố củng không phải là hợp số. 
THUẬT TOÁN - PHÂN TÍCH MỘT SỐ THÀNH TÍCH CÁC THỪA SỐ NGUYÊN TỐ 
N là số nguyên tố thì có cần phân tích nữa không ? Rõ Ràng là không ? Vì sao không ? 
Số nguyên tố là số như thế nào ? 
Giáo sinh: Phan Đức Hoan 
Quá trình phân tích dừng lại khi N[i] là số nguyên tố với N[i] là thương của phép chia N[i-1] cho các số nguyên tố g = 2, 3, 5, 7, 11 
 Đây là điểm lưu ý thứ 3. 
- Những điểm cần lưu ý: 
	+ Nếu N là số nguyên tố thì không cần phân tích nữa. 
	+ Số 1 không phản là số nguyên tố củng không phải là hợp số. 
	 + Quá trình phân tích dừng lại khi N[i] là số nguyên tố với N[i] là thương của phép chia N[i-1] cho các số nguyên tố g = 2, 3, 5, 7, 11 
THUẬT TOÁN - PHÂN TÍCH MỘT SỐ THÀNH TÍCH CÁC THỪA SỐ NGUYÊN TỐ 
Ta đã biết nếu N là số nguyên tố thì không thể phân tích N được nữa vậy quá trình phân tích dừng lại khi nào ? 
Giáo sinh: Phan Đức Hoan 
Ý tưởng thuật toán: 
	- Ta bắt đầu đi từ giá trị đầu tiên của N[i] là N. Ta phải kiểm tra xem N[1]=N có phải là số nguyên tô không. Nếu phải thì thoát và in ra N=N. Nếu không thì ta thức hiện phép chia N[i-1] cho g với g các số nguyên tố có thể có từ 2 cho đến N.Như vậy hai điều kiện ràng buộc cho g ở đây: Một là g phải là một số nguyên tố và N[i-1] phải chia hết cho g. Mỗi một giá trị của mảng A[i] mới sẽ nhận một giá trị của g thỏa mản điều kiện trên. Kết quả là ta sẽ được một mảng các số nguyên tố A[i] mà tích của chúng chính bằng N 
THUẬT TOÁN - PHÂN TÍCH MỘT SỐ THÀNH TÍCH CÁC THỪA SỐ NGUYÊN TỐ 
Trên có sơ trên phân tích trên em nào có thể xây dựng ý tưởng thuật toán này ? 
Giáo sinh: Phan Đức Hoan 
Liệt kê các bước giải: 
	B1: Nhập N 
	B2: Gán i=0,g=1 
	B3: Kiểm tra N[i] có phải là số nguyên tố không. Nếu phải thì dừng và đưa ra kết quả. Sai qua bước 4 
	B4: Gán g=g+1 (g là số nguyên tố) 
	B5: Kiểm tra g là số nguyên tố hay không. Sai về bước 4. Đúng về bước 6 
	B6: Gán N[i] = N[i-1] div g. Về bước 3. 
THUẬT TOÁN - PHÂN TÍCH MỘT SỐ THÀNH TÍCH CÁC THỪA SỐ NGUYÊN TỐ 
Chú ý: g có thể nhận những giá trị số nguyên tố bất kỳ thoả mản điêu kiện 
Em nào có thể trình bày các bước để giải thuật toán này dựa trên những phân tích và ý tưởng đã nêu ? 
Giáo sinh: Phan Đức Hoan 
CỦNG CỐ 
Giáo sinh: Phan Đức Hoan 
DẶN DÒ 
 Về nhà xem lại các bước của thuật giải này, thực hiện phân tích nó qua những ví dụ cụ thể 
 Vẽ lại sơ đồ khối của thuật toán này một cách hoàn chỉnh bằng cách bổ sung vào thuật toán kiểm tra tính nguyên tố của một số thông qua các bước giải 
 Đọc bài tiếp theo, chuẩn bị cho tiết sau. 
Giáo sinh: Phan Đức Hoan 
Cảm ơn các bạn đã lắng nghe ! 
Giáo sinh: Phan Đức Hoan