Bài 1_Phần 3. Phân tích một số tự nhiên thành tích các thừa số nguyên tố

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

I. TOÁN HỌC.

Số nguyên tố là số tự nhiên lớn hơn 1, chỉ có hai ước là 1 và chính nó.
Hợp số là số tự nhiên lớn hơn 1, có nhiều hơn hai ước.
Mọi hợp số đều có thể phân tích được thành tích của các thừa số nguyên tố. N = a^m .b^n .c^p… Trong đó a, b, c là các số nguyên tố , thì N có tất cả số ước số là: (m + 1)(n + 1)(p + 1)…
Cách phân tích hợp số thành tích của các thừa số nguyên tố

Ví dụ 1: Phân tích số 140 thành tích của các thừa số nguyên tố; (có phần nguyên √140=11)

Vậy, số 140 = 2.2.5.7 = 2^2.5.7

Ví dụ 2: Phân tích số 15 thành tích của các thừa số nguyên tố; (có phần nguyên √15=3)

Vậy số 15 = 3.5

Ví dụ 3: Phân tích số 21 thành tích của các thừa số nguyên tố; (có phần nguyên √21=4)

Vậy 21 = 3.7

Ví dụ 4: Phân tích số 450 thành tích của các thừa số nguyên tố; (có phần nguyên √450=21)

Vậy 450 = 2.3.3.5.5 = 2.3^2.5^2

II. THUẬT TOÁN PHÂN TÍCH MỘT SỐ TỰ NHIÊN N>1 THÀNH TÍCH CÁC THỪA SỐ NGUYÊN TỐ.

1) Ghi nhớ

Dạng phân tích ra thừa số nguyên tố của một số nguyên tố là chính nó.
Khi phân tích ra thừa số nguyên tố, trong kết quả thường viết các thừa số theo thứ tự từ bé đến lớn và tích các thừa số giống nhau dạng lũy thừa.

2) Nhận xét các ví dụ ở phần I (Các giá trị ở cột N và cột i):

Sau mỗi lần chia hết cho số i thì giá trị của N giảm đi i lần.
Gá trị của i cuối cùng >= phần nguyên căn bậc hai của N (nếu có) chính là thừa số nguyên tố cuối cùng trong phân tích. Vậy các giá trị của i từ 2 đến căn bậc hai của N.

3) Mô tả thuật toán

Nếu N>1

Lặp i = 2 đến căn bậc hai của N

  Trong khi N chia hết cho một số i nào đó

```
  	N= N/i
```
```
  	Xuất thừa số i
```

  	Nếu N >= i thì thêm dấu nhân sau mỗi thừa số

Nếu N>1 thì N là thừa số nguyên tố cuối cùng trong phân tích

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

using namespace std;

void PT(int N)
{
    if(N>1)
    {
        int i, can=(int)sqrt(N);
        for(i=2; i<=can; i++)
        {
            while(N%i==0)
            {
                N=N/i;
                cout<<i;
                if(N>=i)
                {
                    cout<<"*";
                }
            }
        }

        if(N>1)
        {
            cout<<N;
        }
    }
}
int main()
{
    int N;
    cout<<"N= ";
    cin>>N;
    PT(N);
    return 0;
}

4) Dạng lũy thừa.

Để xuất ra dạng lũy thừa các thừa số, ta đếm số lượng từng thừa số. Nếu có thừa số i (dem>0) thì xuất thừa số i rồi kiểm tra tiếp nếu có từ 2 thừ số i trở lên (dem>1) thì xuất ra lũy thừa của số i và kiểm tra xem nếu vẫn còn thừa số nguyên tố tiếp theo (N>i) thì xuất dấu nhân (*), cuối cùng reset biến dem = 0 để tiếp tục đếm thừa số tiếp theo

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

using namespace std;

void PT(int N)
{
    if(N>1)
    {
        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)
            {
                cout<<i;
                if(dem>1)
                {
                    cout<<"^"<<dem;
                }
                if(N>=i)
                {
                    cout<<"*";
                }
                dem=0;
            }
        }

        if(N>1)
        {
            cout<<N;
        }
    }
}
int main()
{
    int N;
    cout<<"N= ";
    cin>>N;
    PT(N);
    return 0;
}

Kết quả:

5) Sử dụng mảng lưu lại kết quả phân tích.

Kết quả phân tích một số tự nhiên thành tích của các thừa số nguyên tố gồm hai phần là: Phần thừa số và phần lũy thừa (số mũ) nên lựa chọn kiểu dữ liệu pair lưu trữ cặp thừa số và số mũ tương ứng của nó, các cặp được lưu trữ vào mảng vector.

#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;

    if(N>1)
    {
        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;
}
int main()
{
    int N;
    cout<<"N= ";
    cin>>N;
    vector<pair<int,int>> v=PT(N);
    pair <int,int> p;
    int vsize=v.size(), i, luythua;
    for(i=0; i<vsize; i++)
    {
        p=v.at(i);
        cout<<p.first;
        luythua=p.second;
        if(luythua>1)
        {
            cout<<"^"<<luythua;
        }
        if(i<vsize-1)
        {
            cout<<"*";
        }
    }
    return 0;
}