Làm cách nào để tìm thừa số nguyên tố của một số trong python?

Thừa số nguyên tố của một số bất kỳ là thừa số của một số nguyên tố. Các yếu tố khi nhân lên cho bạn một số khác. Số nguyên tố chia hết cho chính nó hoặc cho 1

Nói cách khác, các thừa số nguyên tố được xác định bằng cách tìm xem các số nguyên tố nào nhân với nhau để tạo thành số ban đầu

Thí dụ. Thừa số nguyên tố của 10 là 2 và 5. Điều này là do 2X5 =10 và cả 2,5 đều là số nguyên tố

Trong hướng dẫn này, bạn sẽ học

• Thừa số nguyên tố là gì?
• Tìm các yếu tố chính bằng cách sử dụng phép lặp
• thuật toán sàng
• Các yếu tố chính của Python bằng cách sử dụng phép lặp
• Các yếu tố chính của Python sử dụng đệ quy
• Chương trình nhân tố C Prime sử dụng phép lặp
• Chương trình nhân tố C Prime sử dụng đệ quy

Tìm các yếu tố chính bằng cách sử dụng phép lặp

Để tìm các thừa số nguyên tố của một số đã cho, trước tiên chúng ta lặp lại tất cả các số từ 2 cho đến căn bậc hai của số đó, sau đó kiểm tra xem mỗi số có phải là số nguyên tố không. Miễn là số ban đầu chia hết cho số nguyên tố này, chúng tôi tiếp tục thêm số nguyên tố này với mỗi lần lặp lại

Thí dụ

Mọi số nguyên tố lớn hơn 40 được viết dưới dạng công thức sau. n2+n+41. Vì vậy, chúng ta có thể thay thế n bằng tất cả các số để tìm thừa số nguyên tố tương ứng. e. g. , 02+0+41=41, 12+1+41=43, 22+2+41=47,…

Làm thế nào để in ra thừa số nguyên tố của một số?

• Trong phương pháp này, chúng tôi sẽ lặp lại các số từ 2 cho đến căn bậc hai của số, như đã đề cập trong phần trước
• Để làm được điều đó, chúng ta cần kiểm tra mô đun của số ban đầu trên mỗi số từ 2 cho đến căn bậc hai của n
• Sau đó, ta tìm được danh sách các số nguyên tố là ước của n
• Giải pháp này có độ phức tạp thời gian O(Sqrt(n))

thuật toán

Set a counter i  to 2
While i  <= sqrt(n):
	While n% i  == 0:
		n = n / i  
		print i  
	i  = i  +1
if n > 1:
	print n

thuật toán sàng

Phương pháp sàng phụ thuộc vào việc lưu trữ thừa số nguyên tố nhỏ nhất của các số, giúp giảm đáng kể độ phức tạp khi tính các thừa số nguyên tố cho bất kỳ số nào. Thuật toán sàng tìm tất cả các thừa số nguyên tố có phần hiệu quả

• Khái niệm chính của thuật toán này là lưu trữ thừa số nguyên tố nhỏ nhất của mỗi số cho đến số lớn nhất.
• Chúng tôi lấy số nguyên tố nhỏ nhất cho mỗi số đã cho và thêm nó vào tập hợp các thừa số nguyên tố
• Cuối cùng, chúng ta chia cho số nguyên tố này và lặp lại các bước này cho đến khi đạt 1
• Tất cả điều này được thực hiện với độ phức tạp thời gian O(log(n)), cải thiện hiệu quả của giải pháp rất nhiều
• Điều này cho phép tính toán các thừa số nguyên tố của các số lớn hơn nhiều so với các số mà chúng ta có thể xử lý bằng cách sử dụng phương pháp trước đó

Thí dụ

Cách thứ hai là kiểm tra xem số đó có thể viết dưới dạng 6n-1 hoặc 6n+1 hay không vì mọi số nguyên tố khác 2 và 3 đều có thể viết theo một trong hai công thức. e. g. , 5=6(1)-1, 19=6(3)+1,…

thuật toán

Xác định một mảng mảng để lưu trữ thừa số nguyên tố nhỏ nhất của mỗi số với giá trị chỉ số là giá trị ban đầu cho mọi phần tử của mảng

Set array[1] to 1
Set i to 2
While i*i > max number:
	If array[i] == i:
		Set j to i*i
		While j > max number:
			If array[j] == j:
				Array[j] = i
			j = j + i
	i = i + 1
while the number != 1:
	print array[the number]
	the number = the number / array[the number]

Các yếu tố chính của Python bằng cách sử dụng phép lặp

Ở đây, chúng tôi sẽ hiển thị một đoạn mã bằng ngôn ngữ Python để tìm các thừa số nguyên tố của một số đã cho theo phương pháp lặp

import math
def PrimeFactors(n):
    for i in range(2,int(math.sqrt(n))+1,1):
        while n%i==0:#find all the occurrences of a prime factor
            print((int)(i)),
            n=n/i
    if n!=1:#if the number was originally a prime
        print((int)(n))
n=(int)(input("Enter the number you want: "))
PrimeFactors(n)

đầu ra

Enter the number you want: 4
4

Các yếu tố chính của Python sử dụng đệ quy

Phần này hiển thị một đoạn mã bằng ngôn ngữ Python sử dụng phương pháp sàng để tìm thừa số nguyên tố của một số cho trước

import math
High = (int)(1e5+7)
array=[0 for i in range(High)]
# function to generate all the smallest prime 
def Sieve():
#factors of the numbers until the maximum  number
    for i in range(1, High):
        array[i]=i
    for i in range(2, math.ceil(math.sqrt(High))):
        if (array[i] == i):
            for j in range(i*i, High,i):
                if(array[j]==j):
                    array[j]=i
def PrimeFactors(n):
#We will keep dividing until we reach 1
    if n == 1:
        return
    print((int)(array[n]))
    PrimeFactors((int)(n/array[n]))
#Here we call the function after dividing it by this prime
Sieve()
n=(int)(input("Enter the number you want: "))
PrimeFactors(n)

đầu ra

Enter the number you want: 4
2
2

Chương trình nhân tố C Prime sử dụng phép lặp

Đó là giải pháp tương tự như giải pháp lặp lại python nhưng được viết bằng ngôn ngữ C

Ta yêu cầu người dùng nhập số, sau đó với mỗi số từ 2 đến căn bậc hai của số này, ta cần kiểm tra xem nó có chia hết hay không bằng cách in ra tất cả các lần xuất hiện của thừa số này

#include 
int main()
{
    int n;
    printf("Enter the number you want: ");
    scanf("%d", &n);
    for(int i=2; i*i<=n; i++)
    {
        while(n%i==0)//find all the occurrences of a prime factor
        {
            printf("%d\n",i);
            n/=i;
        }
    }
    if(n!=1)//if the number was originally a prime
    {
        printf("%d",n);
    }
    return 0;
}

đầu ra

Enter the number you want: 2
2

Chương trình nhân tố C Prime sử dụng đệ quy

Đây là giải pháp tương tự như giải pháp đệ quy python nhưng được viết bằng C

Chúng tôi có thể yêu cầu người dùng nhập số; . Cuối cùng, chúng ta gọi hàm đệ quy Thừa số nguyên tố, hàm này chia một số đã cho cho thừa số nguyên tố nhỏ nhất của nó và tự gọi lại cho đến khi đạt đến một

Công thức tìm số nguyên tố trong Python là gì?

Python có chức năng nhân tố không?