Trong bài viết này, chúng ta sẽ xem xét chính xác cách tìm thừa số nguyên tố lớn nhất của một số trong python. Vì vậy, nếu bạn từng thắc mắc làm thế nào để tìm ra con số này một cách chính xác và nhanh chóng bằng ngôn ngữ lập trình hoặc giải bài toán thứ 3 của Dự án Euler
Xin vui lòng, tiếp tục đọc
một yếu tố chính của số là gì?
OK chờ một phút. Trước khi đi sâu vào code để tìm thừa số nguyên tố lớn nhất của một số trong python, chúng ta cần phân tích định nghĩa cốt lõi của một số thừa số nguyên tố
Mọi thứ bắt nguồn từ định lý cơ bản của số học, định lý này nói rằng mọi số nguyên lớn hơn 1 đều có một thừa số duy nhất thành các số nguyên tố
Nhưng chính xác thì “nhân tố hóa” có nghĩa là gì?
Trong toán học, chúng ta nói rằng một số [đối tượng] có phân tích thành thừa số nếu chúng ta viết nó dưới dạng tích của các thừa số thường nhỏ hơn và cùng loại. Vì vậy, nếu chúng ta xem xét, ví dụ, số. 14. Chúng ta có thể viết nó dưới dạng tích của các số nhỏ hơn 2 và 7 vì 2 nhân 7 là 14. có vẻ dễ dàng
Bây giờ, chúng ta biết phân tích thành thừa số là gì. Vì vậy, chúng ta có thể tiếp tục với một số lớn hơn như ví dụ 20?
Ta có 4 nhân 5 là 20, nhưng cũng có 10 nhân 2 là 20 và 2 nhân 2 nhân 5 là 20. Đợi một chút. Chúng tôi nói thừa số duy nhất. Nó hợp lý, bởi vì, nếu bạn tiếp tục phân tích, bạn sẽ bắt đầu thấy rằng mọi số đều có những cách viết khác nhau dưới dạng tích của các số nhỏ hơn và cùng loại
Vì vậy, ĐỘC ĐÁO là chìa khóa, bởi vì bạn chỉ cần có một cách để thực hiện số của mình trong phép chia thành thừa số và các số của bạn không thể là tích của các số nhỏ hơn. Những số đó chúng ta gọi là thừa số nguyên tố và tất nhiên chúng là số tự nhiên và lớn hơn 1
Ok, bây giờ chúng ta đã sẵn sàng đi sâu vào giải bài toán thứ 3 trong Project Euler
Thừa số nguyên tố lớn nhất – Bài toán 3
Các thừa số nguyên tố của 13195 là 5, 7, 13 và 29
Thừa số nguyên tố lớn nhất của số 600851475143 là bao nhiêu?
https. //dự án euler. mạng/vấn đề=3
Trước hết, chúng ta nên tìm tất cả các yếu tố số của chúng tôi. Hãy định nghĩa một hàm trong python, lấy n số và tạo ra tất cả các yếu tố. Sau đó, chúng tôi có thể kiểm tra nó cho các trường hợp đặc biệt của chúng tôi. 13195 và 600851475143. Mỗi khi chúng ta sử dụng hàm max để tìm thừa số lớn nhất của một số
Bây giờ, chúng tôi tìm thấy các yếu tố của mình và chúng tôi đã đưa chúng vào danh sách
Hãy lặp và tìm ước nguyên tố lớn nhất của một số
Dưới đây, bạn sẽ tìm thấy một giải pháp làm thế nào để tìm thừa số nguyên tố lớn nhất của một số. 13195
Và cho một số. 600851475143
Tôi hy vọng rằng nó có thể hữu ích cho bạn theo một cách nào đó. Nếu bạn tò mò, về cách tôi giải quyết vấn đề thứ 2, hãy truy cập liên kết. https. // mạng máy tính. com/how-to-find-the-sum-of-even-fibonacci-numbers-using-python-2-project-euler/
Định dạng đầu vào. Dòng đầu tiên chứa T, số lượng test. Tiếp theo là T dòng, mỗi dòng chứa một số nguyên N
Hạn chế. 1 ≤ T ≤ 10 và 10 ≤ N ≤ 10¹²
Liên kết đến phiên bản Hackerrank
Phân tích
Trước khi đọc qua phần này, tôi khuyến khích bạn nghĩ ra một giải pháp khả thi của riêng bạn trước ~🎀
“Thừa số nguyên tố lớn nhất” hãy chia nhỏ nó và thống nhất một số định nghĩa trước khi phân tích câu đố này
Hệ số. Nếu a chia hết cho N, i. e. không có số dư thì a là một thừa số của N. Ví dụ: 3 là thừa số của 9
Số nguyên tố. Một số là số nguyên tố nếu nó không có thừa số nào ngoài một và chính nó. Trong tiếng anh, một số nguyên tố chỉ có thể chia hết [không cần nhắc] cho 1 và chính nó.
8 không phải là số nguyên tố vì nó có thể chia hết cho 2. Mặt khác, 7 là số nguyên tố vì chỉ có hai số chia hết cho 7 là 7 và 1.
Lớn. Vâng, điều này không cần định nghĩa
Theo các định nghĩa trước đó, một cách để giải quyết vấn đề này là tạo danh sách tất cả các số nguyên tố nhỏ hơn ranh giới 10¹² của chúng ta, sau đó lặp lại nó để tìm số nguyên tố lớn nhất có thể chia hết N đã cho của chúng ta.
Nhưng đó là một giải pháp khá ngây thơ
thừa số nguyên tố
Một cách hiệu quả để giải Project Euler 3, là tính số và lấy hệ số tối đa.
về cơ bản giống như giải pháp ngây thơ ở trên nhưng với cách tiếp cận toán học tốt hơn. mang lại hiệu quả cao hơn.
Với ranh giới 10¹², sàng Eratosthenes tinh chế sẽ giải quyết vấn đề trong thời gian khá chấp nhận được
Đây là triển khai nhận xét của tôi trong Python
Thuật toán rho của Pollard
Bây giờ chúng ta đã đi đến kết luận rằng vấn đề này có thể được giải quyết bằng bất kỳ thuật toán phân tích thừa số nguyên tố nào. Cánh cửa mở ra nhiều thuật toán thú vị và hấp dẫn
Đối với tất cả những người mê lý thuyết số ngoài kia, tôi khuyên bạn nên xem chuỗi câu hỏi này trên Quora nơi mọi người thảo luận về thuật toán phân tích thừa số nguyên tố ưa thích
Thuật toán phân tích thừa số nguyên tố nào nhanh nhất cho đến nay?
Trả lời [1 trên 14]. Chỉnh sửa. Câu hỏi đã thay đổi điều này không thực sự liên quan đến câu hỏi mới. Xem câu trả lời của Arun cho Cái nào…
www. đại số. com
Trong khi đó, đây là giải pháp khiêm tốn của tôi về ProjectEuler3 bằng cách sử dụng thuật toán rho của Pollard
Triển khai Python của thừa số nguyên tố Max bằng thuật toán rho của PollardNếu bạn quan tâm đến một lời giải thích dễ hiểu và hướng dẫn đơn giản về thuật toán rho của Pollard, hãy để lại cho tôi một tin nhắn và tôi sẽ cố gắng viết một bài viết riêng về nó. Trong thời gian chờ đợi, hãy đảm bảo theo dõi tôi trên phương tiện để có thêm các bài xã luận tuyệt vời về Dự án Euler