Thuật toán phân tích một số ra thừa số nguyên tố

     

Bài toán phân tích thừa số nguyên tố, hay nói không hề thiếu hơn là so với số tự nhiên và thoải mái N thành tích những thừa số nguyên tố là 1 trong những bài tập lập trình sẵn cơ bản thường được sử dụng trong số bài thi nhập môn lập trình. Trong bài share này, lập trình không khó sẽ cùng các bạn đi mày mò và xử lý bài toán đối chiếu thừa số thành phần này nhé.

Bạn đang xem: Thuật toán phân tích một số ra thừa số nguyên tố

1. Đề bài bác phân tích thừa số nguyên tố

Nếu bạn lưu ý tên bài xích toán, “phân tích thừa số nguyên tố” đã mang sẵn ý nghĩa sâu sắc của bài bác toán. “thừa số” tất cả ở vào câu: mong mỏi tìm một quá số chưa biết, ta đem tích phân tách cho thừa số sẽ biết ^^; Chẳng hạn, 5 cùng 4 là những 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ố, chúng ta thử nhưng mà xem!

Liên quan: thuật toán phân tích một vài ra thừa số nguyên tố

Như vậy, để dễ dàng hình dung, chúng ta sẽ có những ví dụ sau:

8 = 23100 = 22 * 5999 = 33 * 37

Vậy phương châm 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 những thừa số nguyên tố(chính là phần phía sau vệt bằng).

2. Ý tưởng giải vấn đề phân tích quá số nguyên tố

Rất solo giản, đưa sử bạn phải phân tích số N thành tích những thừa số nguyên tố. Bạn chỉ cần thực hiện chia số N cho các số yếu tắc trong đoạn <2; N>. Với từng số yếu tắc đó, đếm số lần mà số N phân chia hết. Tất nhiên, sau các lần chia cho số i, số N của họ sẽ sụt giảm 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 bọn họ sẽ dừng đâu nhé. Xét một ví dụ khác xem sao:

Giả sử N = 999, lúc N chỉ còn 37, mà 37 là số nguyên tố, bắt buộc 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 bao quát hóa hơn, bạn sẽ dừng quy trình chia lúc số chia to hơn N. Nói cách khác, chừng như thế nào N chưa bởi 1, họ tiếp tục quá trình chia.

Xem thêm: Thả Kraken Có Phải Là Quái Vật Hy Lạp Không? ? Kraken Có Phải Là Quái Vật Hy Lạp Không

3. Code phân tích thừa số nguyên tố

Lời giải thực thi với ngữ điệu C:

Cũng với ý tưởng phát minh này, tuy thế code bởi C++ đang như sau:

Cả 2 code trên lúc chạy sẽ có output như nhau, đấy là một hiệu quả chạy thử:

Nếu các bạn biết về cấu trúc từ điển. Bạn cũng có thể sử dụng chúng để đếm cùng lưu cất giữ để giao hàng khi phải về sau. Với cách này, bạn cũng có thể sử dụng chỉ số mảng để đếm: ví dụ như số 126, mảng đếm là mảng a, khi đó: a<2> = 1, a<3> = 2, a<7> = 1. Mặc dù nhiên, cách này còn có hạn chế là cùng với số N lớn, đang tốn không ít bộ nhớ.

Chạy test với N = 999 xem sao:

Như vậy, 999 = 3^3 * 37.

Một phương pháp tối ưu rộng và dễ ợt hơn là sử dụng cấu trúc map trong C++. Bạn có thể code như sau:

Lưu ý: giải mã này sử dụng biến tự động chỉ bao gồm trong C++ 11 trở lên. Nếu bạn có nhu cầu chạy được thì cần thêm flag: std=c++11.

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

*
Cài để C++11 đến Dev C++

Như vậy, tôi đã dứt bài share phân tích quá số thành phần này. Hy vọng rằng các bạn đã có được những kiến thức thật ngã ích. đầy đủ thắc mắc, hãy vướng lại tại mục bình luận, tôi sẽ giúp đỡ bạn hồ hết gì tất cả thể.

Xem thêm: So Sanh S7 Và S7 Edge Nhật Và Phiên Bản Quốc Tế, So Sánh Samsung Galaxy S7 Edge Và Iphone 7 Plus

> Tham gia diễn đàn Lập Trình Không nặng nề để không bỏ lỡ những nội dung bài viết mới nhất của admin nhé.


Các nội dung bài viết trong khóa họcBài trước: bài 22. Lệnh switch case trong CBài sau: bài bác 24. Tìm kiếm số đảo ngược vào C/C++