Số nguyên tố và phân tích một số tự nhiên thành tích các thừa số nguyên tố.
Nếu
Lặp đến
Trong khi chia hết cho
Xuất thừa số
Nếu (còn thừa số tiếp theo) thì thêm dấu nhân "" sau mỗi thừa số
Nếu thì là thừa số nguyên tố cuối cùng trong phân tích
//C++
#include <bits/stdc++.h>
using namespace std;
void PT(int N)
{
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;
}
Để 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ố (dem>0) thì xuất thừa số rồi kiểm tra tiếp nếu có từ thừ số trở lên (dem>1) thì xuất ra lũy thừa của số và kiểm tra xem nếu vẫn còn thừa số nguyên tố tiếp theo () thì xuất dấu nhân (), cuối cùng reset biến để tiếp tục đếm thừa số tiếp theo.
//C++
#include <bits/stdc++.h>
using namespace std;
void PT(int N)
{
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ả 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.
//C++
#include <bits/stdc++.h>
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;
}
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;
}