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

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

from math import sqrt 

def is_prime[n]: 
    for a in range[2, int[sqrt[n]]]: 
        if n % a == 0: 
            return False 
    return True 

def prime_factors[x]: 
    my_list = [] 
    for no3 in range[2, int[sqrt[x]]]: 
        if x % no3 == 0: 
            # no3 and x/no3 are factors of x 
            if is_prime[no3]: 
                my_list.append[no3] 
            if is_prime[x/no3]: 
                my_list.append[no3] 
    print[max[my_list]] 

Bây giờ khi thử điều này, chúng tôi nhận được

>>> prime_factors[600851475143]
6857
>>> 

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ản

Thừ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ố bằng phương pháp cây thừa số. Phương pháp cây thừa số liên quan đến việc tìm các thừa số của một số và sau đó phân tích các số đó thành thừa số cho đến khi chúng ta đạt được các số nguyên tố. Thực hiện theo các bước dưới đây để xác định thừa số nguyên tố của một số bằng cách sử dụng phương pháp cây thừa số
  1. Coi số là gốc của nhánh trên cùng của cây nhân tố
  2. Sau đó, với tư cách là cành cây, hãy viết ra cặp nhân tố liên quan
  3. Nhân tử hóa các thừa số tổng hợp đã tìm được ở bước 2 và ghi lại cặp thừa số giống như các nhánh tiếp theo của cây
  4. Lặp lại bước thứ 3, trừ khi chúng tôi có được tất cả các yếu tố
• Phương pháp phân chia. Bằng cách chia một số nguyên lớn cho các số nguyên tố, phương pháp chia có thể được sử dụng để xác định các thừa số nguyên tố. Để tìm các thừa số nguyên tố của một số nguyên bằng phương pháp chia, hãy làm theo các bước dưới đây
  1. Chia một số cho số nguyên tố nhỏ nhất sao cho số nguyên tố nhỏ nhất chia hết số đó
  2. Chia thương của bước 1 cho số nguyên tố nhỏ nhất một lần nữa
  3. Lặp lại trừ khi và cho đến khi kết quả thương là 1
  4. Cuối cùng, nhân tất cả các ước của phép chia với tất cả các thừa số nguyên tố

Thừa số nguyên tố lớn nhất - Khái niệm

Khái niệm về thừa số nguyên tố lớn nhất rất đơn giản. Hãy phá vỡ nó

• Mỗi con số bị ảnh hưởng bởi nhiều yếu tố
• Các thừa số là những số chia hết một số đã cho để lại số 0 làm dư
• Chúng ta hãy xem một ví dụ. Khi nhìn vào số 6, chúng ta có thể thấy rằng nó có 4 yếu tố. 1,2,3,6. Mặt khác, hai và ba là các số nguyên tố. 3 là ước nguyên tố lớn nhất của số 6 vì nó lớn hơn 2

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

1. Ở bước đầu tiên, chúng ta phải phân tích đầu vào số đã cho thành thừa số bằng cách chia nó cho ước của một số
2. Bây giờ, chúng ta phải kiểm tra số bằng cách so sánh chúng và đưa ra số cao nhất

Đ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

import math

# input from user 
a = int[input["Enter the number : "]]

maxPrime = 0
# converting the number to odd
while a % 2 == 0:
	maxPrime = 2
	a = a/2	

# prime factors and replacing maxPrimeFactor
for i in range[3, int[math.sqrt[a]] + 1, 2]:
	while a % i == 0:
		maxPrime = i
		a = a / i
if a > 2:
	maxPrime = a
		
print["The largest prime Factor of number is ",int[maxPrime]]
  

Nhập số. 60
Ước nguyên tố lớn nhất của một số là 5

Chương trình Python tìm Thừa số nguyên tố lớn nhất theo số nhập sẵn

def isPrime[a]:
    # invalid input
    if a