Thuật toán thừa số nguyên tố: C, Python Ví dụ
Sarah Chen
Hệ số nguyên tố là gì?
Thừa số nguyên tố của một số đã cho bất kì số là yếu tố đó là một số nguyên tố. Các thừa số khi nhân lên sẽ cho bạn một số khác. Số nguyên tố chia hết cho chính nó hoặc chia hết cho 1.
Nói cách khác, thừa số nguyên tố được xác định bằng cách tìm các số nguyên tố nào nhân với nhau để tạo thành số ban đầu.
Ví dụ: Các 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ố.
Tìm các thừa số nguyên tố bằng cách sử dụng phép lặp
Để tìm thừa số nguyên tố của một số cho trước, 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ố hay không. Miễn là số ban đầu có thể chia hết cho số nguyên tố này, chúng ta tiếp tục cộng số nguyên tố này với mỗi lần lặp.
Ví dụ:
Mọi số nguyên tố lớn hơn 40 được viết theo công thức sau: n2+n+41. Vì vậy, chúng ta có thể thay n bằng tất cả các số để tìm ra thừa số nguyên tố tương ứng. ví dụ: 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 ta 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 .
- Từ đó 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 dựa 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 toán 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ố khá hiệu quả.
- Khái niệm chính của thuật toán này là lưu trữ hệ số nguyên tố nhỏ nhất của mỗi số cho đến số tối đa.
- Chúng ta 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 đến 1.
- Tất cả đều được thực hiện trong độ phức tạp thời gian O(log(n)), cải thiện đáng kể hiệu quả của giải pháp.
- Điều này giúp ta có thể tính được các thừa số nguyên tố của những số lớn hơn nhiều so với những thừa số nguyên tố mà chúng ta có thể xử lý bằng cách sử dụng phương pháp trước đó.
Ví dụ:
Cách thứ hai là kiểm tra xem số đó có thể được viết dưới dạng 6n-1 hay 6n+1 vì bất kỳ số nguyên tố nào ngoài 2 và 3 đều phải được viết theo một trong hai công thức. ví dụ: 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ỉ mục 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]
Python Các yếu tố chính sử dụng phép lặp
Ở đây, chúng tôi sẽ hiển thị một mã trong Python ngôn ngữ để tìm các thừa số nguyên tố của một số cho trước 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
Python Các thừa số nguyên tố sử dụng đệ quy
Phần này hiển thị một mã trong Python Ngôn ngữ bằng phương pháp sàng để tìm các 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 thừa số nguyên tố C sử dụng phép lặp
Đó là giải pháp tương tự như giải pháp lặp python nhưng được viết bằng ngôn ngữ C.
Chúng 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, chúng ta cần kiểm tra xem nó có chia hết được 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 <stdio.h>
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 thừa số nguyên tố C 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ố; sau đó, chúng ta xây dựng mảng số nguyên tố lưu trữ hệ số nguyên tố nhỏ nhất của mỗi số. Cuối cùng, chúng tôi gọi hàm đệ quy Prime Factor, hàm này chia số đã cho cho thừa số nguyên tố nhỏ nhất của nó và gọi lại chính nó cho đến khi đạt đến một.
#include <stdio.h>
int Max = 100007;
int array[100007];
void Sieve()//helping function to generate all the smallest //prime factors of the numbers until the maximum number
{
for(int i=1;i<Max;i++)
{
array[i]=i;
}
for(int i=2;i*i<=Max;i++)
{
if(array[i]==i)
{
for(int j=i*i;j<Max;j+=i)
{
if(array[j]==j)
{
array[j]=i;
}
}
}
}
}
void PrimeFactors(int n)
{
if(n==1)//keep dividing until we reach 1
{
return;
}
printf("%d\n",array[n]);
PrimeFactors(n/array[n]);//call the function after dividing by //this prime
}
int main()
{
Sieve();
int n;
printf("Enter the number you want: ");
scanf("%d", &n);
PrimeFactors(n);
return 0;
}
Đầu ra:
Enter the number you want: 2 2
Một số sự thật thú vị về số Prime
- Một trong những sự thật thú vị nhất là bất kỳ số chẵn nào ngoài 2 đều có thể là tổng của hai số nguyên tố.
- Ví dụ: 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3 … v.v.
- Một thực tế nữa là không có số nguyên tố liên tiếp nào ngoài 2 và 3, vì số nguyên tố chẵn duy nhất là số 2.
- Ngoài ra, tất cả các số nguyên tố ngoại trừ 2 và 3 đều có thể được viết dưới dạng sau: 6 * n + 1 hoặc 6 * n – 1, trong đó n là số nguyên dương.
- Tập hợp các thừa số nguyên tố của một số là duy nhất.
- Số 1 không phải là số nguyên tố cũng không phải hợp số.
- Việc phân tích các số thành thừa số nguyên tố có thể giúp giải quyết các vấn đề như tính chia hết, rút gọn phân số và tìm mẫu số chung của các phân số khác nhau.
- Ngoài ra, một trong những ứng dụng thú vị của hệ số nguyên tố là phá vỡ các mã bí mật dựa trên số.
