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 tương đối đầy đủ hơn là đối chiếu 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 xây dựng cơ bản thường được sử dụng trong các bài thi nhập môn lập trình. Vào bài share này, thiết kế không khó khăn sẽ cùng chúng ta đi tò mò và giải quyết và xử lý bài toán so sánh thừa số yếu tắc 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 phân tích quá số nguyên tố

Nếu bạn lưu ý tên bài bác toán, “phân tích quá số nguyên tố” đã với sẵn ý nghĩa của bài toán. “thừa số” gồm ở trong câu: hy vọng tìm một vượt số chưa biết, ta đem tích phân tách cho vượt số đang 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 những thừa số sẽ luôn là số nguyên tố, bạn thử cơ mà xem!

Như vậy, để dễ hình dung, chúng ta sẽ bao gồm ví dụ sau:

8 = 23100 = 22 * 5999 = 33 * 37

Vậy mục tiêu của các bạn là: Nhập vào một trong những 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 câu hỏi phân tích quá số nguyên tố

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

Giả sử N = 999, khi N chỉ từ 37, mà lại 37 là số nguyên tố, bắt buộc ta dừng quy trình chia.

999 3 333 3 111 3 37 37 1

Khi đó, 999 = 33 * 37.

Nói một cách tổng thể hóa hơn, bạn sẽ dừng quy 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, họ tiếp tục quy trình chia.

Xem thêm: Vì Sao Phần Lớn Lục Địa Ôxtrâylia Là Hoang Mạc ? Vì Sao Phần Lớn Diện Tích Lục Địa Ô

3. Code đối chiếu thừa số nguyên tố

Lời giải thực thi với ngôn ngữ C:

Cũng với phát minh này, nhưng lại code bởi C++ đã như sau:

Cả 2 code trên khi chạy sẽ có output như nhau, đó là một công dụng chạy thử:

Nếu chúng ta biết về cấu tạo từ điển. Bạn cũng có thể sử dụng bọn chúng để đếm với lưu giữ gìn để ship hàng khi yêu cầu về sau. Với phương pháp này, bạn có thể sử dụng chỉ số mảng nhằm đếm: chẳng hạn như số 126, mảng đếm là mảng a, lúc đó: 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 tương đối nhiều bộ nhớ.

Chạy thử với N = 999 coi sao:

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

Một giải pháp tối ưu hơn và thuận lợi hơn là sử dụng cấu trúc map vào C++. Chúng ta cũng có thể code như sau:

Lưu ý: giải mã này thực hiện biến auto chỉ gồm trong C++ 11 trở lên. Nếu bạn muốn chạy được thì nên cần thêm flag: std=c++11.

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

*
Cài đặt C++11 mang đến Dev C++

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

> Tham gia forums Lập Trình Không cực nhọc để không bỏ dở những bài viết mới độc nhất của admin nhé.

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