Có một số cách để tìm và in các thừa số của một số, cách đầu tiên là lặp qua từng số cho đến 'N' và kiểm tra bằng cách chia nó xem nó có chia hết cho nó hay không. Đây là một cách tiếp cận ngây thơ và mất nhiều thời gian cho các giá trị rất lớn của 'N'. Cách tiếp cận hiệu quả và tốt hơn là lặp qua bình phương của số 'N' [đã bao gồm] nếu 'N' không chẵn i. e. lẻ khác độc quyền [bạn sẽ biết ngay]. Cách tiếp cận này làm giảm độ phức tạp của O[n] thành O[√n]. Hãy bắt đầu với việc tìm thừa số của một số N trong Python3
Tìm thừa số của một số trong Python
Đầu tiên, hãy thử sử dụng cách tiếp cận ngây thơ
N=int[input[]]
factors=[1]
for i in range[2,N]:
if[N%i==0]:
factors.append[i]
factors.append[N]
print[factors]Output: 24 [1, 2, 3, 4, 6, 8, 12, 24]
Độ phức tạp thời gian=O[n]
cách tiếp cận hiệu quả
Một cách tiếp cận hiệu quả để tìm các thừa số của số N. Kiểm tra xem số đó có phải là số chính phương hay không và thay vì lặp từ 1 đến N, lặp lại đến căn bậc hai [N]. Ý tưởng là tìm mô đun của N và kiểm tra xem nó có chia hết hay không, nếu có, hãy bao gồm ước số trong danh sách thừa số cũng như thương trong danh sách thừa số. Vấn đề phát sinh nếu số dường như là một hình vuông hoàn hảo, chúng tôi sẽ nhận được các bản sao tại thời điểm này bằng cách sử dụng cùng một cách tiếp cận, ví dụ:. lấy N=36 bây giờ cho 6 nó chia hết nên nó cũng sẽ thêm thương 6 và sẽ có hai số 6 và chúng tôi không muốn điều này do đó chúng tôi không bao gồm căn bậc hai [N] trong phép lặp. Lưu ý hai điểm dưới đây
- Nếu N không phải là số chính phương lặp qua căn bậc hai[N]+1
- Nếu không lặp qua căn bậc hai [N]
Chúng tôi cũng có thể sử dụng set để lưu trữ các yếu tố nhưng sau đó sẽ có nhiều lần lặp hơn +1 so với sử dụng danh sách do đó tôi khuyên bạn nên sử dụng phương pháp này
Việc triển khai python 3 cho phương pháp trên được đưa ra bên dưới, nhưng tôi khuyên tất cả các bạn nên tự mình thử cách này và sau đó xem mã để hỗ trợ nếu bạn gặp khó khăn
Bài viết này được tạo ra để đề cập đến một số chương trình trong Python, để tìm và in các thừa số của một số do người dùng nhập vào trong thời gian chạy. Dưới đây là danh sách các phương pháp được sử dụng
- Tìm thừa số của một số bằng vòng lặp while
- Sử dụng cho vòng lặp
- Sử dụng chức năng
Lưu ý - Thừa số của một số nói n là số chia hết cho số [n]. Ví dụ, thừa số của 12 là 1, 2, 3, 4, 6, 12. Sáu số này chia hết cho 12 không chừa số dư
Tìm thừa số của một số bằng vòng lặp while
Để tìm thừa số của bất kỳ số nào trong Python, bạn phải yêu cầu người dùng nhập một số, sau đó tìm và in ra thừa số của nó như trong chương trình dưới đây. Câu hỏi đặt ra là viết chương trình Python tìm thừa số của một số bằng vòng lặp while. Đây là câu trả lời của nó
print["Enter the Number: "] num = input[] num = int[num] print["\nFactors of", num] i = 1 while i