Nhập một số nguyên dương để biểu diễn dưới dạng tích các thừa số nguyên tố:
Số nguyên tố là số tự nhiên chỉ có hai ước số dương phân biệt là 1 và chính nó. Các số có nhiều hơn 2 ước số dương được gọi là hợp số.
Định lý: "Mọi số tự nhiên lớn hơn 1 đều phân tích được thành tích những thừa số nguyên tố, và sự phân tích này là duy nhất nếu không kể đến thứ tự của các thừa số".
Để phân tích một số ra thừa số nguyên tố, ta thử chia lần lượt số đó cho các số nguyên tố như 2, 3, 5, 7, ...
Đề bài: Nhận 1 số nguyên n từ bàn phím, sau đó phân tích số nguyên dương n ra các thừa số nguyên tố. Yêu cầu viết hàm phân tích số nguyên n ra thừa số nguyên tố bằng kỹ thuật chương trình con. Tên hàm là phanTichThuaSoNguyenTo. Ví dụ:
- 18 = 2 3 3
- 32 = 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
- 33 = 3 11
Bài giải:
#include
void phanTichThuaSoNguyenTo[int n]{ i = 2;
while [n>1]{
if [n%i==0]{
printf["%d ",i];
n=n/i;
}
else{
i
int main[]{
int n;
printf["nhap so n: "];
scanf["%d",&n];
printf["%d = ",n]; phanTichThuaSoNguyenTo[n]; 0;
}
Xem Video: Phan tich so nguyen n ra thua so nguyen to
Đề bài: Phân tích một số thành tích các thừa số nguyên tố
Với bài này các bạn cần nhớ lại thừa số nguyên tố là gì và cách phân tích một số ra thừa số nguyên tố.
Tích các thừa số nguyên tố chính là phép nhân giữa các số với nhau trong đó tất cả các số đều là số nguyên tố. Ví dụ: 10 = 2 * 5. Trong đó 2 và 5 là các số nguyên tố.
18 = 2 * 3 * 3. Trong đó 2 và 3 là các số nguyên tố.
Cách phân tích ra thừa số nguyên tố:
Ở các lớp cấp 1 và 2 gì đó mình không nhớ rõ, chúng ta đã được học rồi. Chúng ta sẽ thực hiện các phép chia liên tiếp số cần phân tích cho các số nguyên tố đến khi nào thương là 1 thì dừng lại. Ví dụ phân tích số 140.
Chúng ta lấy 140 chia 2 [2 là số nguyên tố] được 70. Thấy 70 vẫn chia được cho 2 nên ta chia tiếp được 35. Thấy 35 không chia hết cho 2 nữa, số nguyên tố tiếp theo là 3 cũng không chia hết mà chia hết cho 5 nên ta chia cho 5 được 7. Đến đây 7 chia 7 được 1. Thương là 1 nên ta dừng lại. Vậy 140 = 2 * 2 * 5 * 7
Vậy là chúng ta đã nhớ lại cách làm. Tổng kết lại là chúng ta lấy số đó chia cho các số nguyên tố nhưng có thể lặp lại. Trong khi vẫn chia hết cho số 2 thì cứ chia đến khi nào không chia được thì tìm số khác để chia và cũng làm như vậy.
Nhưng làm sao để biết được các số nguyên tố nào sẽ được dùng để chia? Với các số bé như các ví dụ này chúng ta có thể nhẩm nhanh được, nhưng với các số lớn hơn thì chúng ta khó nhẩm được và cũng không phải là số nguyên tố nào cũng có thể dùng, ví dụ như số 140 chúng ta không có dùng đến số 3 dù số 3 là số nguyên tố. Đơn giản là chúng ta chọn những số mà thương hiện tại của chúng ta có thể chia hết bằng cách dùng vòng lặp để duyệt và kiểm tra hết các số từ 2 đến n [n là số cần phân tích]. Vậy giờ thử code theo hướng mà chúng ta đã suy nghĩ xem sao.
/** * Nhap vao 1 so tu nhien va phan tich ra thua so nguyen to */ #include #include int isPrime[int n] { int i; int m = [int] sqrt[n]; for [i = 2; i