Phân tích một số thành tích các thừa số nguyên tố bằng code C++
Bài toán: Nhập vào một số nguyên dương, hãy phân tích số nguyên dương đó thành tích các thừa số nguyên tố.
- Input
-
1Nhap vao so nguyen n: 120
- Output
-
12 2 2 3 5
Ý tưởng phân tích một số thành tích các thừa số nguyên tố.
Ở các lớp dưới chúng ta đã biết được cách phân tích một số thành các thừa số nguyên tố. Bằng cách cứ chia số n đến khi nào thương bằng 1 thì dừng lại.Ví dụ ta phân tích số 12 thành các thừa số như sau:
|
1 2 3 4 5 6 |
120 / 2 60 / 2 30 / 2 15 / 3 5 / 5 1 |
Vậy ta sẽ viết một hàm kiểm tra các số nguyên tố, trong vòng lặp for(int i=0;i<=n;i++) nếu i là số nguyên tố thì ta tiến hành lấy số n chia cho i. Cứ lặp lại đến khi nào không thể chia cho i được nữa thì thôi !
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
#include<iostream> using namespace std; bool nguyento(int n) { if (n <= 1) return false; for (int i = 2; i <= sqrt(n); i++) if (n%i == 0) return false; return true; } int main(){ int n; cout << "Nhap vao so nguyen n: "; cin >> n; for(int i=2;i<=n;i++) while (n%i == 0 && nguyento(i) ) { cout << i << " "; n /= i; } system("pause"); return 0; } |
Sau khi chạy chương trình trên ta có kết quả.
|
1 2 |
Nhap vao so nguyen n: 12 2 2 3 |
Cải thiện chương trình
Nhưng các bạn có thể thấy nếu chia số 120 đến khi không thể chia hết cho 2 được nữa. Vậy ta có cần phải xét chia hết cho những số như: 4, 6, 8, 10…không ? Câu trả lời là không vì nếu chia hết cho 4, 6, 8 thì đã chia hết cho 2 rồi. Nếu chia 120 đến khi không thể chia hết cho 3 được nữa thì cũng không thể chia hết cho những số như 6, 9, 12…Thuật toán này có vẻ giống sàng nguyên tố nhỉ ? Chúng ta hãy thử xem
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include<iostream> using namespace std; int main(){ int n; cout << "Nhap vao so nguyen n: "; cin >> n; for(int i=2;i<=n;i++) while (n%i == 0 ) { cout << i << " "; n /= i; } system("pause"); return 0; } |
Sau khi chạy chương trình trên ta vẫn thấy kết quả đúng như mong đợi.
|
1 2 |
Nhap vao so nguyen n: 12 2 2 3 |
Nếu các bạn chưa biết thuật toán sàng nguyên tố là gì thì có thể xem tại đây.
Bài viết mình đến đây cũng kết thúc. Cám ơn các bạn đã theo dõi !
