Bài Tập Java Số 12: Phân Tích Số Nguyên Thành Các Thừa Số Nguyên Tố

Đề bài

Input: Nhập vào một số nguyên dương n >=2.
Output: Phân tích n thành các thừa số nguyên tố. Ví dụ: Số 28 được phân tích thành 2 x 2 x 7.

Giải thuật

Ta lấy n lần lượt chia cho các số nguyên dương i theo thứ tự tăng dần từ 2 cho đến n. Nếu n chia hết cho i thì i chính là thừa số nguyên tố của n, và gán n bằng một giá trị mới chính là thương của phép chia n chia i.

Nếu giá trị mới của n vẫn tiếp tục chia hết cho giá trị i đó thì ta lại lặp lại như trên. Chừng nào n không chia hết cho i đó nữa thì ta mới tăng i lên và xét tiếp.

Code mẫu

package baitap12;

import java.util.Scanner;

public class baitap12 {

 public static void main(String[] args) {
    int n;   
    Scanner nhap = new Scanner(System.in);
    System.out.println("Nhap so nguyen: ");
    n = nhap.nextInt();
    while(n<2)
    {
       System.out.println("Ban vua nhap mot so khong hop le.Vui long nhap lai: ");
       n = nhap.nextInt();
    }
    for(int i=2; i<=n;i++)
    {
       while(n%i==0)
       {
          n=n/i;
          if(n==1)
              System.out.print(i);
          else
              System.out.print(i+" x ");
       }
       if (n==1)
          break;
    }
 }
}