Viết chương trình phân tích thừa số nguyên tố trong java

Đề bài viết chương trình phân tích thừa số nguyên tố của một số nguyên dương, hôm nay tienanhvn sẽ trình bày cho các bạn về thuật toán phân tích ra các thừa số nguyên tố và từ thuật toán đó các bạn sử dụng lập trình java để thực hiện chương trình phân tích ra các thừa số nguyên tố.

Ví dụ thừa số nguyên tố

28 = 2 x 2 x 7
140 = 2 x 2 x 5 x 7

Đầu vào của bài toán

Nhập n số nguyên dương n = 140

Đầu ra của chương trình

140 = 2 x 2 x 5 x 7

Ý tưởng giải quyết bài toán.

Viết hàm kiểm tra số nguyên tố
Viết hàm phân tích ra các thừa số nguyên tố
khai báo hàm main

Thuật toán phân tích thừa số nguyên tố

Dùng vòng lặp for [2:n] if phần tử i là số nguyên tố và n%i ==0 thì in ra thừa số nguyên tố.

Chương trình phân tích thừa số nguyên tố.

Hàm kiểm tra số nguyên tố

boolean checkNguyenTo(int n){
if(n <=2){
return true;
}else{
for(int i = 2; i<=Math.sqrt(n);i++){
if(n%i == 0){
return false;
}
}
}
return true;
}

Hàm phân tích thừa số nguyên tố

void phantichthuasonguyento(int n){
for(int i=2;i<=n;i++){
while(checkNguyenTo(i) && (n%i ==0)){
System.out.print(" "+i);
n/=i;
}
}
}

Hàm main

public static void main(String args[]){
Phantichthuasonguyento pt = new Phantichthuasonguyento();
int n = 140;
pt.phantichthuasonguyento(n);
}

Toàn bộ code chương trình.

package baitap3;
public class Phantichthuasonguyento {
boolean checkNguyenTo(int n){
if(n <=2){
return true;
}else{
for(int i = 2; i<=Math.sqrt(n);i++){
if(n%i == 0){
return false;
}
}
}
return true;
}
void phantichthuasonguyento(int n){
for(int i=2;i<=n;i++){
while(checkNguyenTo(i) && (n%i ==0)){
System.out.print(" "+i);
n/=i;
}
}
}
public static void main(String args[]){
Phantichthuasonguyento pt = new Phantichthuasonguyento();
int n = 140;
pt.phantichthuasonguyento(n);
}
}