Bài 23. Phân tích thừa số nguyên tố trong C/C++

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

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

3002
1502
755
155
33
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.

9993
3333
1113
3737
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:

Cũng với ý tưởng này, nhưng code bằng C++ sẽ như sau:

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ểnBạ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ớ.

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:

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.

Hoặc nếu bạn dùng Dev C++, hãy vào Tools -> Compile Options và chọn như ảnh sau:

Cài đặt C++11 cho Dev C++
Cài đặt C++11 cho Dev C++

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

avatar
  Subscribe  
newest oldest most voted
Notify of
Hưng Nguyễn Quang
Member
Hưng Nguyễn Quang

thuật toán này có độ phức tạp bao nhiêu anh

Huyền trần
Guest
Huyền trần

cho em hỏi thêm flag:std=c++11 như thế nào ạ?
vì em có chọn trong compiler dòng có c++11 rồi nhưng vẫn không dùng được hàm to_string() và stoi().
em cảm ơn ạ.

Hùng
Guest
Hùng

“nguyên tố” chỉ rằng các thừa số sẽ luôn là số nguyên tố, bạn thử mà xem! Câu này có nghỉa là gì ạ em không hiểu

Thuận Hữu
Guest
Thuận Hữu

Anh ơi if(dem){…….} có nghĩa là sao thế ạ