Phân tích một số ra thừa số nguyên tố c++

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 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

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 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

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!

I. Các kiến thức cần nhớ

Phân tích một số ra thừa số nguyên tố

Ví dụ: Số \(76\) được phân tích như sau:

Như vậy \(76 = {2^2}.19\)

Nhận xét:

* Cách tính số lượng các ước của một số $m\left( {m > 1} \right)$:  ta xét dạng phân tích của số m ra thừa số nguyên tố:

Nếu $m = {a^x}$ thì $m$  có $x + 1$ ước

Nếu $m = {a^x}.{b^y}$ thì $m$  có $\left( {x + 1} \right)\left( {y + 1} \right)$ ước.

Nếu $m = {a^x}.{b^y}.{c^z}$ thì $m$  có $\left( {x + 1} \right)\left( {y + 1} \right)\left( {z + 1} \right)$ ước.

II. Các dạng toán thường gặp

 Dạng 1: Phân tích các số cho trước ra thừa số nguyên tố

Phương pháp

Ta thường  phân tích một số tự nhiên $n\left( {n > 1} \right)$ ra thừa số nguyên tố bằng cách phân tích theo hàng dọc.

Dạng 2 : Ứng dụng phân tích một số ra thừa số nguyên tố để tìm các ước của số đó.

Phương pháp

+ Phân tích số cho trước ra thừa số nguyên tố.

+ Chú ý rằng nếu $c = a.b$  thì $a$  và $b$ là hai ước của $c.$

Nhớ lại rằng: $a = b.q$\( \Leftrightarrow a \vdots b \Leftrightarrow a \in B\left( b \right)\) và \(b \in \)Ư\(\left( a \right)\) $(a,b,q \in N,b \ne 0)$

Dạng 3: Bài toán đưa về việc phân tích một số ra thừa số nguyên tố

Phương pháp:

 Phân tích đề bài, đưa về việc tìm ước của một số cho trước bằng cách phân tích số đó ra thừa số nguyên tố.

Đề 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.

140 | 2 70 | 2 35 | 5 7 | 7 1

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 <= m; i++) { if(n % i == 0) return 0; } return 1; } int main() { int n, i; printf("Enter number n = "); scanf("%d", &n); printf("%d = ", n); for (i = 2; i <= n; i++) { while( isPrime(i) && (n % i == 0) ) { printf("%d.", i); n = n / i; } } return 0; }

Như code trên các bạn thấy chúng ta đã làm theo đúng như các bước trên. Lưu ý là có 1 hàm để kiểm tra số nguyên tố nhé.

Tuy nhiên thì code bên trên có thể rút gọn đi rất nhiều. Các bạn thử suy nghĩ một chút trước khi đọc tiếp nhé.

Các bạn để ý là khi chúng ta đã chia 140 cho 2 đến khi không thể chia cho 2 được nữa thì chắc chắn nó không chia hết cho 4, 6, 8… vì nếu chia hết cho 4,6,8… thì chắc chắn nó chia hết cho 2. Tương tự khi kiểm tra đã khồn còn có thể chia hết cho 3 thì sẽ không thể chia hết cho 6,9,12… Từ đó ta nhận thấy là các số phía sau thì n không bao giờ chia hết nếu nó là bội của các số đã kiểm tra mà chỉ có thể chia hết cho các số chưa kiểm tra, mà các số chưa kiểm tra đó chính là các số nguyên tố. Do vậy chúng ta sẽ không cần kiểm tra các số có là số nguyên tố hay không. Code của chúng ta sẽ gọn hơn rất nhiều mà kết quả không hề sai.

/** * Nhap vao 1 so tu nhien va phan tich ra thua so nguyen to */ #include #include int main() { int n, i; printf("Enter number n = "); scanf("%d", &n); printf("%d = ", n); for (i = 2; i <= n; i++) { while(n % i == 0) { printf("%d.", i); n /= i; } } return 0; }

Rất đơn giản phải không! ^^. Nếu bạn nào để ý thì thuật toán này dựa trên thuật toán sàng nguyên tố.