Bài Tập Java Số 4: Kiểm Tra Một Số Nguyên Tố

Đề Bài:

Input: Nhập vào một số nguyên n ≥ 1
Output: Yes nếu n là số nguyên tố, no nếu n không phải là số nguyên tố.

Giải Thuật:

Số nguyên tố là số tự nhiên chỉ có các ước số là 1 và chính nó. Do 1 chỉ có 1 ước số là chính nó, nên 1 không phải là số nguyên tố.

 Như ta đã biết 1 số bị chia chia hết được cho số chia khi số chia nhỏ hơn hoặc bằng số bị chia và n cũng không thể chia hết cho bất kỳ số nguyên nào nằm trong khoảng (n/2;n).

 Vậy ta chỉ sẽ xét trong đoạn [2;n/2] nếu n chia hết cho bất kỳ số nguyên nào nằm trong đoạn này thì nó không phải là số nguyên tố còn ngược lại thì n là số nguyên tố.

 Code Mẫu:

package baitap4;

import java.util.Scanner;

public class baitap4 {

 public static void main(String[] args) {
  int n;
  Scanner nhap = new Scanner(System.in);
  System.out.println("Nhap so nguyen n lon hon hoac bang 1: ");
  n = nhap.nextInt();
  while (n<1)
  {
      System.out.println("n phai lon hon hoac bang 1. Nhap lai: ");
      n = nhap.nextInt();
  }
  if (n==1) 
   System.out.println("No");
  else if (n==2)
   System.out.println("Yes");
  else
  {
   int dem = 0;
   for (int i = 2; i<=n/2; i++)
   {
    if (n%i == 0)
     dem++;
   }
   if (dem == 0)
      System.out.println("Yes");
   else
    System.out.println("No"); 
  }
 }
}