PHÂN TÍCH CÁC SỐ TỰ NHIÊN THÀNH TÍCH CÁC THỪA SỐ NGUYÊN TỐ

I. GIỚI THIỆU VỀ SỐ HỌC

1. Số Nguyên Tố: Là số tự nhiên lớn hơn 1, chỉ có hai ước số là 1 và chính số đó.
2. Hợp Số: Là số tự nhiên lớn hơn 1 và có nhiều hơn hai ước.
3. Phân Tích Hợp Số: Mọi hợp số đều có thể phân tích thành tích của các thừa số nguyên tố theo dạng: N = a^m * b^n * c^p ... Trong đó, a, b, c là các số nguyên tố. Số ước của N được tính là: (m + 1)(n + 1)(p + 1)...

1. Cách Phân Tích Hợp Số Thành Các Thừa Số Nguyên Tố

Ví Dụ:

• Ví dụ 1: Phân tích số 140:

  • Căn bậc hai của 140 là √140 = 11 (phần nguyên).
  • Vậy, 140 = 2 * 2 * 5 * 7 = 2^2 * 5 * 7.

• Ví dụ 2: Phân tích số 15:

  • Căn bậc hai của 15 là √15 = 3.
  • Vậy, 15 = 3 * 5.

• Ví dụ 3: Phân tích số 21:

  • Căn bậc hai của 21 là √21 = 4.
  • Vậy, 21 = 3 * 7.

• Ví dụ 4: Phân tích số 450:

  • Căn bậc hai của 450 là √450 = 21.
  • Vậy, 450 = 2 * 3 * 3 * 5 * 5 = 2 * 3^2 * 5^2.

II. THUẬT TOÁN PHÂN TÍCH HỢP SỐ THÀNH THỪA SỐ NGUYÊN TỐ

1) Ghi Nhớ Quan Trọng

• Số nguyên tố khi phân tích sẽ là chính nó.
• Kết quả phân tích thường được sắp xếp từ bé đến lớn và các thừa số giống nhau được ghi dưới dạng lũy thừa.

2) Nhận Xét Từ Các Ví Dụ Ở Phần I

1. Sau mỗi lần chia hết cho số i, giá trị của N giảm xuống bằng i.
2. Giá trị của i cuối cùng (nếu có) sẽ lớn hơn hoặc bằng phần nguyên của căn bậc hai của N, đó là thừa số nguyên tố cuối cùng.

3) Mô Tả Thuật Toán

• Nếu N > 1:
  • Lặp từ i = 2 đến căn bậc hai của N:
    • Khi nào N chia hết cho số i:
      • N = N / i
      • Xuất ra thừa số i
      • Nếu N >= i, thêm dấu nhân sau thừa số.
• Nếu N > 1, thì N là thừa số nguyên tố cuối.

4) Xuất Kết Quả Dưới Dạng Lũy Thừa

Để xuất dạng lũy thừa của các thừa số, ta đếm số lượng từng thừa số i và xuất theo số lượng.

5) Sử Dụng Mảng Để Lưu Kết Quả Phân Tích

Kết quả sẽ được lưu trữ dưới dạng cặp thừa số và số mũ tương ứng:

#include <iostream>
#include <math.h>
#include <vector>

using namespace std;

vector<pair<int,int>> PT(int N)
{
    pair <int,int> p;
    vector<pair<int,int>> v;

    int i, can=(int)sqrt(N);
    int dem=0;
    for(i=2; i<=can; i++)
    {
        while(N%i==0)
        {
            dem++;
            N=N/i;
        }
        if(dem>0)
        {
            p.first=i;
            p.second =dem;
            v.push_back(p);
            dem=0;
        }
    }
    if(N>1)
    {
        p.first=N;
        p.second =1;
        v.push_back(p);
    }
    return v;
}

Kết Quả:

Khi xuất kết quả, các thừa số và lũy thừa sẽ được hiển thị rõ ràng và dễ hiểu cho người đọc.
source: viblo