Cách tìm thừa số nguyên tố lớn nhất của một số trong python
Ngôn ngữ lập trình Python là ngôn ngữ lập trình cấp cao và hướng đối tượng. Python là một ngôn ngữ lập trình cấp cao mạnh mẽ, dễ học. Nó có một cách tiếp cận đơn giản nhưng hiệu quả đối với lập trình hướng đối tượng Show
Thừa số nguyên tố của một số là ước của số đó là số nguyên tố Tìm thừa số nguyên tố lớn nhất của một số Chúng tôi sẽ lấy một số nguyên làm đầu vào từ người dùng và sau đó tìm thừa số nguyên tố lớn nhất của số Ví dụ Input: N = 21 Output: 7 Prime factors of 21 = 3, 7. Largest of them is 7. Chúng tôi sẽ tìm tất cả các thừa số nguyên tố của một số và sau đó trả về số lớn nhất trong tất cả Để tìm thừa số nguyên tố lớn nhất, trước tiên chúng ta sẽ kiểm tra xem số đó có chia hết cho 2 không, i. e. thậm chí. Nếu có, hãy biến nó thành số lẻ và khởi tạo maxPrimeFactor = 2 Sau đó, với mỗi số từ 3, hãy tìm tất cả các ước của số đó (đầu tiên sẽ là số nguyên tố) -> khởi tạo maxPrimeFactor với ước số. Và chia số cho nó cho đến khi nó không còn chia hết cho số. Làm như vậy sẽ đảm bảo mọi bội số của số nguyên tố này sẽ không thể chia hết cho số Tìm thừa số nguyên tố lớn nhất là một khái niệm rất đơn giản. Giả sử số đó là 1092. Tất cả các thừa số nguyên tố của 1092 là 2, 2, 3, 7, 13. Vậy thừa số nguyên tố lớn nhất là 13. Để tìm thấy điều này, thuật toán sau đây có thể được sử dụng number = num Step 1: If num is divisible by 2, store largest prime factor as 2. keep on dividing num until it is not divisible by 2. After each division, update num as num/2. Step 2: At this point, num must be odd. Starting with 3 to square root of num, if divisible, divide and update num, and update largest prime factor. Step 3: if the modified num is greater than 2, update the largest prime factor with num. Tìm thừa số nguyên tố lớn nhất của một sốVí dụ dưới đây minh họa các thuật toán trên import math def MaxPrime(num): CurrMaxPrime = -1 #If num is divisible by 2, store CurrMaxPrime #as 2. keep on dividing num until it is not #divisible by 2. After each division, update #num as num/2. if(num % 2 == 0): CurrMaxPrime = 2 while(num % 2 == 0): num = num/2 #At this point, num must be odd. Starting with #3 to square root of num , if divisible, divide #and update num, and update CurrMaxPrime for i in range (3, int(math.sqrt(num)) + 1, 2): while(num % i == 0): CurrMaxPrime = i num = num/i #if the modified num is greater than 2, #update the CurrMaxPrime with num if (num > 2): CurrMaxPrime = num return CurrMaxPrime x = 42 y = 1092 z = 695467363456 print("Largest prime factor of", \ x, "is:", MaxPrime(x)) print("Largest prime factor of", \ y, "is:", MaxPrime(y)) print("Largest prime factor of", \ z, "is:", MaxPrime(z)) Đoạn mã trên sẽ cho đầu ra sau Largest prime factor of 42 is: 7.0 Largest prime factor of 1092 is: 13 Largest prime factor of 695467363456 is: 5433338777.0 Mỗi vòng lặp của bạn có từ 2 đến n, vì vậy với 2 vòng lặp, vòng lặp của bạn phải được chạy trong bình phương (n) lần trước khi đưa ra câu trả lời cho bạn Nếu bạn thay đổi vòng lặp của mình một chút, bạn có thể làm cho nó nhanh hơn nhiều. Để tìm các thừa số của một số n, bạn không cần phải kiểm tra tất cả các số nhỏ hơn n. Nó là đủ nếu bạn kiểm tra tối đa int(sqrt(n)). Đối với mỗi thừa số x nằm trong khoảng từ 2 đến int(sqrt(n)), n/x cũng sẽ là một thừa số Vì vậy, bằng cách thay đổi vòng lặp của bạn để chỉ chạy tối đa int(sqrt(n)), mã của bạn sẽ chạy nhanh hơn nhiều
Bây giờ khi thử điều này, chúng tôi nhận được Trong bài viết này, chúng ta sẽ có trải nghiệm thực tế để tìm thừa số nguyên tố lớn nhất của một số với sự trợ giúp của Lập trình Python bằng hai cách tiếp cận khác nhau Thừa số nguyên tố - Giới thiệu cơ bảnThừa số nguyên tố bằng phương pháp cây thừa số và lấy thừa số nguyên tố bằng phương pháp chia
Thừa số nguyên tố lớn nhất - Khái niệmKhái niệm về thừa số nguyên tố lớn nhất rất đơn giản. Hãy phá vỡ nó
Bây giờ chúng ta đã sẵn sàng đi sâu vào phiên bản lập trình tìm thừa số nguyên tố lớn nhất của một số Cách tiếp cận Python để tìm thừa số nguyên tố lớn nhất của một sốĐể tìm thừa số nguyên tố lớn nhất của một số, chúng ta sẽ thực hiện theo hai cách tiếp cận khác nhau. Cách tiếp cận đầu tiên là lấy đầu vào từ người dùng và cách tiếp cận thứ hai là nhập trước số trong chính mã. Trước tiên chúng ta hãy xem cách tiếp cận thuật toán của chương trình thuật toán
Đoạn mã Chương trình Python để tìm thừa số nguyên tố lớn nhất bằng cách lấy đầu vào của người dùng
Chương trình Python tìm Thừa số nguyên tố lớn nhất theo số nhập sẵn
Mô tả mã Trước khi chúng ta có thể tính toán một số, trước tiên chúng ta phải xác định tất cả các biến ảnh hưởng đến nó. Ví dụ, khi xem xét số 60, chúng ta có thể thấy rằng nó được tạo thành từ ba yếu tố. 2,3,5. Một vòng lặp từ 2 đến một nửa số được chạy trong mã. Vòng lặp sẽ từ 2 đến 7 trong trường hợp này. Bây giờ chúng ta sẽ xem liệu mỗi thừa số có phải là số nguyên tố không. Chúng tôi có một hàm trợ giúp trong mã để kiểm tra xem một số nguyên có phải là số nguyên tố hay không — chúng tôi gọi nó trên mọi thừa số. Chúng tôi thêm số vào danh sách các thừa số được bảo toàn nếu nó vừa là thừa số vừa là số nguyên tố. Cuối cùng, chúng tôi lấy số cao nhất từ danh sách để có thừa số nguyên tố lớn nhất Phần kết luậnTrong phần hướng dẫn này, chúng ta đã biết thế nào là phân tích thừa số nguyên tố, Cách tính thừa số nguyên tố lớn nhất của một số và hai cách tiếp cận khác nhau để tìm ra thừa số nguyên tố lớn nhất của một số. Cách tiếp cận đầu tiên là lấy đầu vào của người dùng và cách tiếp cận thứ hai là bằng các số được nhập trước trong chính mã Thừa số nguyên tố lớn nhất của số 600851475143 Mã Python là gì?Câu trả lời là. 6857 . Vì mỗi số nguyên có thể được biểu diễn (phân tích thừa số) bằng cách sử dụng các số nguyên tố như 2^a*3^b*5^c…. Chúng ta có thể bỏ qua phép thử nguyên tố và chỉ cần sử dụng một vòng lặp đơn giản để tìm kiếm thừa số nguyên tố lớn nhất.
thừa số nguyên tố lớn nhất là gì?Theo quy ước, 1 (trước đây được coi là số nguyên tố, nhưng bây giờ được gọi là đơn vị) đôi khi được coi là số nguyên tố lớn nhất của chính nó . Trên thực tế, 1 là tích rỗng (được định nghĩa là đơn vị nhân, i. e. 1) số nguyên tố. |