Phân tích thừa số nguyên tố trong C++

• • Theo công thức toán học để phân tích thừa số nguyên tố ta áp dụng 2 cách sau:
  • 1. Rẽ nhánh: sau đây là ví dụ phân tích số 72 ra thừa số nguyên tố bắng cách lấy 72 chia các số nguyên tố( 2, 3 ,5 , 7….)
  • 2. Cột dọc:
  • Thuật toán :
  • TH1
  • Cho i chạy từ 2 đến \sqrt{n}
  • Trong khi (n % i ==0). In i
  • Gán n = n/i
  • TH 2
  • ho i chạy từ 2 đến \sqrt{n}
  • Trong khi (n % i ==0). In i
  • Gán n = n/i
  • Trường kết quả  cuối cùng không chia hết cho số nguyên tố nào và khác 1 thì in n
  • Nếu ( n != 1). In n
  • Mô tả thuật toán
  • Code C++
  • TH1

 
#include <bits/stdc++.h>
using namespace std;

void pt( int n)
{
	for (int i = 2 ; i <= sqrt(n); i++){
		while(n % i == 0){
		     cout << i << " ";
		     n/=i;
		}
	}
}
int main()
{
	int n;
	cin >> n;
	pt(n);
	return 0;
}

– Kết quả:

– TH2:

 
#include <bits/stdc++.h>
using namespace std;

void pt( int n)
{
	for (int i = 2 ; i <= sqrt(n); i++){
		while(n % i == 0){
				cout << i << " ";
				n/=i;
		}
	}
	if (n != 0)
		cout << n;
}
int main()
{
	int n;
	cin >> n;
	pt(n);
	return 0;
}

– Kết quả:

• • TH3: Thừa số được liệt kê kèm theo số mũ:
  • Code C++

 
#include <bits/stdc++.h>
using namespace std;

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

– Kết quả:

• • TH 4
  • Code C++

 
#include <bits/stdc++.h>
using namespace std;

void pt( int n)
{
	for (int i = 2 ; i <= sqrt(n); i++){
		int dem = 0;
			while(n % i == 0){
				++dem;
				n/=i;
			}
			if(dem){
            	cout << i;
            if(dem > 1) 
				cout << "^" << dem;
            if(n > i){
                cout << " * ";
			}
	}
	if ( n != 0)
		cout << n;
	}
}
int main()
{
	int n;
	cin >> n;
	pt(n);
	return 0;
}

– Kết quả: