thuật toán phân tích một số ra thừa số nguyên tố

Bài toán phân tách quá số yếu tố, hoặc thưa không thiếu rộng lớn là phân tách số đương nhiên N kết quả những quá số yếu tố là 1 trong những bài bác tập luyện xây dựng cơ phiên bản thông thường được dùng trong số bài bác thi đua nhập môn xây dựng. Trong bài bác share này, Lập trình ko khó khăn tiếp tục nằm trong chúng ta đi kiếm hiểu và xử lý câu hỏi phân tách quá số yếu tố này nhé.

1. Đề bài bác phân tách quá số nguyên vẹn tố

Nếu các bạn nhằm ý thương hiệu câu hỏi, “phân tích quá số nguyên vẹn tố” đang được đem sẵn chân thành và ý nghĩa của câu hỏi. “thừa số” sở hữu ở vô câu: ham muốn thám thính một quá số chưa chắc chắn, tao lấy tích phân chia cho tới quá số đang được biết ^^; Chẳng hạn, 5 và 4 là những quá số vô luật lệ nhân 5×4 = đôi mươi. “nguyên tố” chỉ rằng những quá số tiếp tục luôn luôn là số yếu tố, các bạn demo tuy nhiên xem!

Bạn đang xem: thuật toán phân tích một số ra thừa số nguyên tố

Như vậy, nhằm dễ dàng tưởng tượng, tất cả chúng ta sẽ sở hữu những ví dụ sau:

  • 8 = 23
  • 100 = 22 * 5
  • 999 = 33 * 37

Vậy tiềm năng của chúng ta là: Nhập vô một vài nguyên vẹn dương N, hãy phân tách số N kết quả những quá số nguyên vẹn tố(chính là phần hâu phương vết bằng).

2. Ý tưởng giải câu hỏi phân tách quá số nguyên vẹn tố

Rất giản dị và đơn giản, fake sử bạn phải phân tách số N kết quả những quá số yếu tố. quý khách chỉ việc triển khai phân chia số N cho những số yếu tố trong khúc [2; N]. Với từng số yếu tố cơ, kiểm điểm số thứ tự tuy nhiên số N phân chia không còn. Tất nhiên, sau từng thứ tự phân chia cho tới số i, số N của tất cả chúng ta tiếp tục sụt giảm i thứ tự.

Một ví dụ sống động rộng lớn, xét N = 300

300 2
150 2
75 5
15 5
3 3
1

Khi cơ, 300 = 22 * 52 * 3. Nhưng ko cần Khi N = 1 tất cả chúng ta tiếp tục ngừng đâu đấy. Xét một ví dụ không giống coi sao:

Giả sử N = 999, Khi N chỉ với 37, tuy nhiên 37 là số yếu tố, nên tao ngừng quy trình phân chia.

999 3
333 3
111 3
37 37
1

Khi cơ, 999 = 33 * 37.

Nói một cơ hội tổng quát mắng hóa rộng lớn, các bạn sẽ ngừng quy trình phân chia Khi số phân chia to hơn N. Nói cách thứ hai, chừng này N ko bởi vì 1, tất cả chúng ta nối tiếp quy trình phân chia.

3. Code phân tách quá số nguyên vẹn tố

Lời giải xây dựng với ngữ điệu C:

Xem thêm: phần mềm quản lý chi tiêu cá nhân tiếng việt

#include <stdio.h>

int main(){
    int n;
    printf("\nNhap n = ");
    scanf("%d", &n);
    int dem;
    
    for(int i = 2; i <= n; i++){
        dem = 0;
        while(n % i == 0){
            ++dem;
            n /= i;
        }
        if(dem){
            if(dem > 1) printf("%d^%d", i, dem);
            else printf("%d", i);
            if(n > i){
                printf(" * ");
            }
        }
    }
    
}

Cũng với ý tưởng phát minh này, tuy nhiên code bởi vì C++ tiếp tục như sau:

#include <iostream>
using namespace std;


int main(){
    int n;
    cout << "\nNhap n = ";
    cin >> n;
    int dem;
    
    for(int i = 2; i <= n; i++){
        dem = 0;
        while(n % i == 0){
            ++dem;
            n /= i;
        }
        if(dem){
            cout << i;
            if(dem > 1) cout << "^" << dem;
            if(n > i){
                cout << " * ";
            }
        }
    }
    
}

Cả 2 code bên trên Khi chạy sẽ sở hữu output như nhau, đó là một thành phẩm chạy thử:

Nhap n = 126
2 * 3^2 * 7

Nếu các bạn biết về cấu hình từ điểnBạn rất có thể dùng bọn chúng nhằm kiểm điểm và lưu tích lại nhằm đáp ứng Khi cần thiết về sau. Với phương pháp này, bạn cũng có thể dùng chỉ số mảng nhằm đếm: Chẳng hạn như số 126, mảng kiểm điểm là mảng a, Khi đó: a[2] = 1, a[3] = 2, a[7] = 1. Tuy nhiên, cơ hội này còn có giới hạn là với số N rộng lớn, tiếp tục tốn thật nhiều bộ lưu trữ.

#include <iostream>
using namespace std;

const int MAX = 10000;
int dem[MAX];
int main(){
    int N;
    cout << "\nNhap n = ";
    cin >> N;
    int n = N; // Tao ban sao cua N
    if(n > MAX){
        printf("Ban nhap sánh lon hon %d", MAX);
        return 0;
    }
    for(int i = 0; i <= n; i++) dem[i] = 0;
    for(int i = 2; i <= n; i++){
        while(n % i == 0){
            ++dem[i];
            n /= i;
        }
    }
    for(int i = 0; i <= N; i++){
        if(dem[i]){
            cout << i << " ^ " << dem[i] << "\n";
        }
    }
}

Chạy demo với N = 999 coi sao:

Nhap n = 999
3 ^ 3
37 ^ 1

Như vậy, 999 = 3^3 * 37.

Một cơ hội tối ưu rộng lớn và thuận tiện rộng lớn là dùng cấu hình map trong C++. Chúng tao rất có thể code như sau:

#include <iostream>
using namespace std;
#include <map>

int main(){
    int N;
    cout << "\nNhap n = ";
    cin >> N;
    
    map<int, int> m;
    for(int i = 2; i <= N; i++){
        while(N % i == 0){
            m[i]++;
            N /= i;
        }
    }
    
    for(auto it : m){
        cout << it.first << " " << it.second << "\n";
    }
}

Lưu ý: Lời giải này dùng phát triển thành tự động hóa chỉ mất vô C++ 11 trở lên trên. Nếu mình thích chạy được thì nên tăng flag: std=c++11.

Xem thêm: đề thi học sinh giỏi văn 7 cấp huyện violet

g++ -std=c++11 your_file.cpp -o your_program

Hoặc nếu như bạn sử dụng Dev C++, hãy vô Tools -> Compile Options và lựa chọn như hình họa sau:

Cài đặt điều C++11 cho tới Dev C++
Cài đặt điều C++11 cho tới Dev C++

Như vậy, tôi đang được triển khai xong bài bác share phân tách quá số yếu tố này. Hi vọng rằng những bạn đã sở hữu được những kỹ năng và kiến thức thiệt hữu dụng. Mọi vướng mắc, hãy nhằm lại bên trên mục comment, tôi tiếp tục giúp đỡ bạn những gì rất có thể.

> Tham gia diễn đàn Lập Trình Không Khó nhằm ko bỏ qua những nội dung bài viết tiên tiến nhất của admin nhé.