Thuật toán thừa số nguyên tố: C, Python Ví dụ

Hệ số nguyên tố là gì?

Thừa số nguyên tố của một số là thừa số mà bản thân nó cũng là một thừa số nguyên tố. số nguyên tốChỉ chia hết cho 1 và chính nó.

Ví dụ: Các thừa số nguyên tố của 10 là 2 và 5, vì 2 × 5 = 10.

Tìm các thừa số nguyên tố bằng cách sử dụng phép lặp

Lặp từ 2 đến sqrt(n) và kiểm tra tính chia hết. Trong khi n chia hết cho ứng viên hiện tại, hãy thực hiện phép chia và in ra.

Ví dụ: mọi số nguyên tố lớn hơn 40 đều phù hợp với n²+n+41, vậy n = 0, 1, 2 cho kết quả 41, 43, 47.

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

• Lặp lại các số từ 2 đến sqrt(n).
• Kiểm tra phần dư của n với từng ứng viên; phần dư bằng 0 có nghĩa là ứng viên đó là một thừa số nguyên tố.
• Thu thập tất cả các số nguyên tố chia hết cho n.
• Thủ tục này chạy với độ 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 lưu trữ thừa số nguyên tố nhỏ nhất của mọi số, tối đa đến một giới hạn nhất định, giúp giảm đáng kể chi phí phân tích thừa số sau khi tính toán trước.

• Ghi lại ước số nguyên tố nhỏ nhất của mỗi số nguyên, đến giới hạn tối đa.
• Lấy số nguyên tố nhỏ nhất đó và thêm nó vào tập hợp các thừa số.
• Chia số đó cho số nguyên tố đó và lặp lại cho đến khi đạt đến 1.
• Mỗi truy vấn chạy trong khoảng O(log n).

Ví dụ: Một số nguyên tố khác 2 và 3 có dạng 6n-1 hoặc 6n+1. Ví dụ, 5 = 6(1)-1 và 19 = 6(3)+1.

Thuật toán: định nghĩa một mảng Nó lưu trữ thừa số nguyên tố nhỏ nhất của mỗi số, sử dụng chỉ số làm giá trị ban đầu cho mỗi phần tử.

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]

Bài viết liên quan

• Cấu trúc dữ liệu đồ thị và Algorithms
• Vấn đề nhân viên bán hàng đi du lịch
• Thuật toán phương pháp phân tách
• Thuật toán sắp xếp nhóm

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

Sau đây Python Đoạn mã này tìm các thừa số nguyên tố bằng phương pháp thử và chia lặp đi lặp lại:

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
2
2

Python Các thừa số nguyên tố sử dụng đệ quy

Python Đoạn mã bên dưới sử dụ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)]

# generate smallest prime factors
def Sieve():
    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):  # divide until we reach 1
    if n == 1:
        return
    print((int)(array[n]))
    PrimeFactors((int)(n / array[n]))

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

Giải pháp lặp tương tự được viết trong C: nhập một số, sau đó với mỗi ứng viên từ 2 đến sqrt(n), kiểm tra tính chia hết và in ra mọi lần xuất hiện của thừa số nguyên tố.

#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

Phiên bản đệ quy C phản ánh Python Một: xây dựng mảng các thừa số nguyên tố nhỏ nhất, sau đó lặp lại phép chia cho thừa số đó cho đến khi n đạt đến 1.

#include <stdio.h>
int Max = 100007;
int array[100007];

void Sieve()  // smallest prime factors up to Max
{
    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)  // divide until we reach 1
        return;
    printf("%d\n", array[n]);
    PrimeFactors(n / array[n]);
}

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

• Bất kỳ số chẵn nào khác 2 đều có thể được viết dưới dạng tổng của hai số nguyên tố (4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3).
• Không có số nguyên tố nào liên tiếp khác ngoài 2 và 3, vì 2 là số nguyên tố chẵn duy nhất.
• Mọi số nguyên tố ngoại trừ 2 và 3 đều có dạng 6n + 1 hoặc 6n − 1, trong đó n là một 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 là số hợp số.
• Phân tích thừa số nguyên tố giúp kiểm tra tính chia hết, đơn giản hóa phân số và tìm mẫu số chung.
• Phân tích thừa số nguyên tố cũng là nền tảng của các mã mật mã dựa trên số.

Câu Hỏi Thường Gặp