Bài toán phân tích thừa số nguyên tố bằng ngôn ngữ C/C++ là một bài toán lập trình khá hay. Trong bài viết hôm nay, mình sẽ giới thiệu cho bạn đọc cách giải bài toán này
1. Số nguyên tố là gì? Phân tích thừa số nguyên tố là như thế nào?
Số nguyên tố là số chỉ chia hết cho 1 và chính nó.
Ví dụ: 2, 3, 5, 7. . .
Bạn đang xem: Viết chương trình phân tích một số nguyên thành các thừa số nguyên tố
Phân tích thừa số nguyên tố tức là phân tích một số nguyên cho trước thành tích của các số nguyên tố.
Ví dụ: 20 phân tách thành 2*2*5 30 phân tách thành 2*3*5
2. Bài toán phân tích thừa số nguyên tố của số nguyên n
Đề bài: Nhập vào số nguyên n từ bàn phím n>1, in ra màn hình dãy các số nguyên tố được phân tách bởi số nguyên n sắp xếp theo chiều tăng dần, mỗi số cách nhau một dấu cách.
Ví dụ:
Tích của các số ở kết quả của bài toán chính là số nguyên ban đầu được nhập vào từ bàn phím.
3. Giải quyết bài toán phân tích thừa số nguyên tố bằng ngôn ngữ C/C++
3.1 Giới thiệu thuật toán
Thuật toán đưa ra dựa trên phương pháp chia lần lượt cho các số nguyên tố nhỏ hơn N theo chiều từ nhỏ đến lớn. Tức là chia cho số nguyên tố nhỏ nhất, nếu phép chia hết, chúng ta nhận 1 giá trị, kết quả của phép chia sẽ gán thành N, nếu không chia hết, chúng ta tiếp tục chia giá trị N cho số nguyên tố lớn hơn.
Để thực hiện được việc chia cho các số nguyên tố từ nhỏ đến lớn, ta cho N chia cho các số lần lượt tử 2 đến N, thuật toán sẽ bỏ qua số không phải là số nguyên tố (n) vì số không phải là số nguyên tố sẽ chia hết cho số nguyên tố nhỏ hơn nó(n), do đó đương nhiên N sẽ chia hết cho số nguyên tố nhỏ hơn (n) nào đó.
Chúng ta cần khai báo một mảng để lưu giá trị mỗi lần N chia hết cho số đó.
3.2 Code trong C
Code trong C và C++ chỉ khác nhau một số cấu trúc cơ bản, về mặt thuật toán thì không có gì khác biệt.
Nhìn vào thuật toán mình chia sẻ có vẻ hơi khó hiểu, bạn hãy nhìn vào những dòng code dưới đây để hiểu chi tiết hơn nhé!
#includevoid thuasonguyento(long &n){scanf("%d",&n);long a<100000>; //mang a de dung gia trilong c=0;while(n>1){for(long i=2;i
Kết quả chạy thử:
3.3 Code trong C++
C++ là nâng cao của C nên cấu trúc có khác một chút.
Xem thêm: Kiểm Tra Học Kì Ii Văn 7 Đề Kiểm Tra Văn 7 Học Kì 2 Theo Hình Thức: Tự Luận
#includeusing namespace std;void thuasonguyento(long &n){cin>>n;long a<100000>;long c=0;while(n>1){for(long i=2;i
Kết quả chạy thử vd 2:
Trên đây là toàn bộ cách giải bài toán phân tích thừa số nguyên tố bằng ngôn ngữ C/C++
Mọi vướng mắc trong quá trình giải bài tập bạn đọc comment xuống phía dưới để được hỗ trợ.
Bài toán phân tích thừa số nguyên tố bằng ngôn ngữ C/C++ là một bài toán lập trình khá hay. Trong bài viết hôm nay, mình sẽ giới thiệu cho bạn đọc cách giải bài toán này
1. Số nguyên tố là gì? Phân tích thừa số nguyên tố là như thế nào?
Số nguyên tố là số chỉ chia hết cho 1 và chính nó.
Ví dụ: 2, 3, 5, 7. . .
Phân tích thừa số nguyên tố tức là phân tích một số nguyên cho trước thành tích của các số nguyên tố.
Ví dụ: 20 phân tách thành 2*2*5
30 phân tách thành 2*3*5
2. Bài toán phân tích thừa số nguyên tố của số nguyên n
Đề bài: Nhập vào số nguyên n từ bàn phím n>1, in ra màn hình dãy các số nguyên tố được phân tách bởi số nguyên n sắp xếp theo chiều tăng dần, mỗi số cách nhau một dấu cách.
Ví dụ:
Tích của các số ở kết quả của bài toán chính là số nguyên ban đầu được nhập vào từ bàn phím.
3. Giải quyết bài toán phân tích thừa số nguyên tố bằng ngôn ngữ C/C++
3.1 Giới thiệu thuật toán
Thuật toán đưa ra dựa trên phương pháp chia lần lượt cho các số nguyên tố nhỏ hơn N theo chiều từ nhỏ đến lớn. Tức là chia cho số nguyên tố nhỏ nhất, nếu phép chia hết, chúng ta nhận 1 giá trị, kết quả của phép chia sẽ gán thành N, nếu không chia hết, chúng ta tiếp tục chia giá trị N cho số nguyên tố lớn hơn.
Để thực hiện được việc chia cho các số nguyên tố từ nhỏ đến lớn, ta cho N chia cho các số lần lượt tử 2 đến N, thuật toán sẽ bỏ qua số không phải là số nguyên tố (n) vì số không phải là số nguyên tố sẽ chia hết cho số nguyên tố nhỏ hơn nó(n), do đó đương nhiên N sẽ chia hết cho số nguyên tố nhỏ hơn (n) nào đó.
Chúng ta cần khai báo một mảng để lưu giá trị mỗi lần N chia hết cho số đó.
3.2 Code trong C
Code trong C và C++ chỉ khác nhau một số cấu trúc cơ bản, về mặt thuật toán thì không có gì khác biệt.
Nhìn vào thuật toán mình chia sẻ có vẻ hơi khó hiểu, bạn hãy nhìn vào những dòng code dưới đây để hiểu chi tiết hơn nhé!
#include<stdio.h> void thuasonguyento(long &n){ scanf("%d",&n); long a[100000]; //mang a de dung gia tri long c=0; while(n>1){ for(long i=2;i<=n;i++){ while(n%i==0){ //neu n chia het cho i thi lay gia tri i n=n/i; a[c]=i; c++; //them gia tri thi phai tang c } } } for(long i=0;i<c;i++){ // dinh dang in ra man hinh thoi hiha if(i!=c-1) printf("%d ",a[i]); if(i==c-1) printf("%d",a[i]); } } int main(){ long n; thuasonguyento(n); //goi ham ra ne return 0; }
Kết quả chạy thử:
3.3 Code trong C++
C++ là nâng cao của C nên cấu trúc có khác một chút.
#include<iostream> using namespace std; void thuasonguyento(long &n){ cin>>n; long a[100000]; long c=0; while(n>1){ for(long i=2;i<=n;i++){ while(n%i==0){ n=n/i; a[c]=i; c++; } } } for(long i=0;i<c;i++){ if(i!=c-1) cout<<a[i]<<" "; if(i==c-1) cout<<a[i]; } } int main(){ long n; thuasonguyento(n); return 0; }
Kết quả chạy thử vd 2:
Trên đây là toàn bộ cách giải bài toán phân tích thừa số nguyên tố bằng ngôn ngữ C/C++
Mọi vướng mắc trong quá trình giải bài tập bạn đọc comment xuống phía dưới để được hỗ trợ.
Chúc bạn học tập thành công!
This entry is part 21 of 69 in the series Học C Không Khó
82 / 100
Bài toán phân tích thừa số nguyên tố, hay nói đầy đủ hơn là phân tích số tự nhiên N thành tích các thừa số nguyên tố là một bài tập lập trình cơ bản thường được sử dụng trong các bài thi nhập môn lập trình. Trong bài chia sẻ này, Lập trình không khó sẽ cùng các bạn đi tìm hiểu và giải quyết bài toán phân tích thừa số nguyên tố này nhé.
1. Đề bài phân tích thừa số nguyên tố
Nếu bạn để ý tên bài toán, “phân tích thừa số nguyên tố” đã mang sẵn ý nghĩa của bài toán. “thừa số” có ở trong câu: muốn tìm một thừa số chưa biết, ta lấy tích chia cho thừa số đã biết ^^; Chẳng hạn, 5 và 4 là các thừa số trong phép nhân 5×4 = 20. “nguyên tố” chỉ rằng các thừa số sẽ luôn là số nguyên tố, bạn thử mà xem!
Như vậy, để dễ hình dung, chúng ta sẽ có những ví dụ sau:
- 8 = 23
- 100 = 22 * 5
- 999 = 33 * 37
Vậy mục tiêu của các bạn là: Nhập vào một số nguyên dương N, hãy phân tích số N thành tích các thừa số nguyên tố(chính là phần phía sau dấu bằng).
2. Ý tưởng giải bài toán phân tích thừa số nguyên tố
Rất đơn giản, giả sử bạn cần phân tích số N thành tích các thừa số nguyên tố. Bạn chỉ cần thực hiện chia số N cho các số nguyên tố trong đoạn [2; N]. Với mỗi số nguyên tố đó, đếm số lần mà số N chia hết. Tất nhiên, sau mỗi lần chia cho số i, số N của chúng ta sẽ giảm đi i lần.
Một ví dụ sinh động hơn, xét N = 300
| 300 | 2 |
| 150 | 2 |
| 75 | 5 |
| 15 | 5 |
| 3 | 3 |
| 1 |
Khi đó, 300 = 22 * 52 * 3. Nhưng không phải khi N = 1 chúng ta sẽ dừng đâu nhé. Xét một ví dụ khác xem sao:
Giả sử N = 999, khi N chỉ còn 37, mà 37 là số nguyên tố, nên ta dừng quá trình chia.
| 999 | 3 |
| 333 | 3 |
| 111 | 3 |
| 37 | 37 |
| 1 |
Khi đó, 999 = 33 * 37.
Nói một cách tổng quát hóa hơn, bạn sẽ dừng quá trình chia khi số chia lớn hơn N. Nói cách khác, chừng nào N chưa bằng 1, chúng ta tiếp tục quá trình chia.
3. Code phân tích thừa số nguyên tố
Lời giải triển khai với ngôn ngữ C:
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#include <stdio.h> int main(){ int n; printf("\nNhap n = "); scanf("%d", &n); int dem; for(int i = 2; i <= n; i++){ dem = 0; while(n % i == 0){ ++dem; n /= i; } if(dem){ if(dem > 1) printf("%d^%d", i, dem); else printf("%d", i); if(n > i){ printf(" * "); } } } } |
Cũng với ý tưởng này, nhưng code bằng C++ sẽ như sau:
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <iostream> using namespace std; int main(){ int n; cout << "\nNhap n = "; cin >> n; int dem; for(int i = 2; i <= n; i++){ dem = 0; while(n % i == 0){ ++dem; n /= i; } if(dem){ cout << i; if(dem > 1) cout << "^" << dem; if(n > i){ cout << " * "; } } } } |
Cả 2 code trên khi chạy sẽ có output như nhau, đây là một kết quả chạy thử:
Nếu bạn biết về cấu trúc từ điển. Bạn có thể sử dụng chúng để đếm và lưu giữ lại để phục vụ khi cần về sau. Với cách này, bạn có thể sử dụng chỉ số mảng để đếm: Chẳng hạn như số 126, mảng đếm là mảng a, khi đó: a[2] = 1, a[3] = 2, a[7] = 1. Tuy nhiên, cách này có hạn chế là với số N lớn, sẽ tốn rất nhiều bộ nhớ.
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <iostream> using namespace std; const int MAX = 10000; int dem[MAX]; int main(){ int N; cout << "\nNhap n = "; cin >> N; int n = N; // Tao ban sao cua N if(n > MAX){ printf("Ban nhap so lon hon %d", MAX); return 0; } for(int i = 0; i <= n; i++) dem[i] = 0; for(int i = 2; i <= n; i++){ while(n % i == 0){ ++dem[i]; n /= i; } } for(int i = 0; i <= N; i++){ if(dem[i]){ cout << i << " ^ " << dem[i] << "\n"; } } } |
Chạy thử với N = 999 xem sao:
Như vậy, 999 = 3^3 * 37.
Một cách tối ưu hơn và thuận tiện hơn là sử dụng cấu trúc map trong C++. Chúng ta có thể code như sau:
|
0 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; #include <map> int main(){ int N; cout << "\nNhap n = "; cin >> N; map<int, int> m; for(int i = 2; i <= N; i++){ while(N % i == 0){ m[i]++; N /= i; } } for(auto it : m){ cout << it.first << " " << it.second << "\n"; } } |
Lưu ý: Lời giải này sử dụng biến auto chỉ có trong C++ 11 trở lên. Nếu bạn muốn chạy được thì cần thêm flag: std=c++11.
g++ -std=c++11 your_file.cpp -o your_program |
Hoặc nếu bạn dùng Dev C++, hãy vào Tools -> Compile Options và chọn như ảnh sau:
Như vậy, tôi đã hoàn thành bài chia sẻ phân tích thừa số nguyên tố này. Hi vọng rằng các bạn đã có được những kiến thức thật bổ ích. Mọi thắc mắc, hãy để lại tại mục bình luận, tôi sẽ giúp bạn những gì có thể.
> Tham gia forum Lập Trình Không Khó để không bỏ lỡ những bài viết mới nhất của admin nhé.