Thuật toán tìm số nguyên tố trong java

Tìm số nguyên tố đơn giản

Dưới đây là một ví dụ thuật toán tìm số nguyên tố bằng Java:

public class PrimeNumbers {
   public static void main(String[] args) {
      int n = 50;
      System.out.println("Các số nguyên tố nhỏ hơn " + n + " là:");
      for(int i = 2; i < n; i++) {
         if(isPrime(i)) {
            System.out.print(i + " ");
         }
      }
   }
  
   public static boolean isPrime(int num) {
      if(num < 2) {
         return false;
      }
      for(int i = 2; i <= Math.sqrt(num); i++) {
         if(num % i == 0) {
            return false;
         }
      }
      return true;
   }
}

Trong ví dụ này, hàm isPrime được sử dụng để kiểm tra xem một số có phải là số nguyên tố hay không. Nó sử dụng một vòng lặp để kiểm tra xem có bất kỳ số nào nhỏ hơn căn bậc hai của số đó chia hết cho số đó hay không. Nếu có, số đó không phải là số nguyên tố và hàm trả về giá trị false. Nếu không, số đó là số nguyên tố và hàm trả về giá trị true.

Ở trong hàm main, một vòng lặp được sử dụng để lặp qua các số từ 2 đến n-1. Với mỗi số đó, hàm isPrime được gọi để kiểm tra xem số đó có phải là số nguyên tố hay không. Nếu số đó là số nguyên tố, nó sẽ được in ra trên màn hình.

Tìm số nguyên tố từ 1 đến n

Đây là một ví dụ thuật toán tìm các số nguyên tố từ 1 đến n bằng Java:

public class PrimeNumbers {
   public static void main(String[] args) {
      int n = 50;
      System.out.println("Các số nguyên tố từ 1 đến " + n + " là:");
      for(int i = 2; i <= n; i++) {
         if(isPrime(i)) {
            System.out.print(i + " ");
         }
      }
   }
  
   public static boolean isPrime(int num) {
      if(num < 2) {
         return false;
      }
      for(int i = 2; i <= Math.sqrt(num); i++) {
         if(num % i == 0) {
            return false;
         }
      }
      return true;
   }
}

Trong ví dụ này, hàm isPrime được sử dụng để kiểm tra xem một số có phải là số nguyên tố hay không, tương tự như trong ví dụ trước đó.

Ở trong hàm main, một vòng lặp được sử dụng để lặp qua các số từ 2 đến n. Với mỗi số đó, hàm isPrime được gọi để kiểm tra xem số đó có phải là số nguyên tố hay không. Nếu số đó là số nguyên tố, nó sẽ được in ra trên màn hình.

Sàng nguyên tố với Java

Sàng nguyên tố là một thuật toán hiệu quả để tìm tất cả các số nguyên tố trong một khoảng cách cho trước. Đây là một ví dụ về sàng nguyên tố bằng Java:

public class SieveOfEratosthenes {
   public static void main(String[] args) {
      int n = 50;
      boolean[] prime = new boolean[n+1];
      Arrays.fill(prime, true);
      
      for(int p = 2; p*p <= n; p++) {
         if(prime[p] == true) {
            for(int i = p*p; i <= n; i += p) {
               prime[i] = false;
            }
         }
      }
      
      System.out.println("Các số nguyên tố từ 1 đến " + n + " là:");
      for(int i = 2; i <= n; i++) {
         if(prime[i] == true) {
            System.out.print(i + " ");
         }
      }
   }
}

Trong ví dụ này, một mảng boolean prime được tạo ra để lưu trữ trạng thái của các số từ 2 đến n, với giá trị true nếu số đó là số nguyên tố và false nếu không. Mảng này được khởi tạo với tất cả các phần tử đều có giá trị true.

Sau đó, vòng lặp đầu tiên được sử dụng để duyệt qua các số từ 2 đến căn bậc hai của n. Với mỗi số đó, nếu nó là số nguyên tố, tất cả các bội của nó lớn hơn hoặc bằng p*p (vì tất cả các bội nhỏ hơn đã được đánh dấu trước đó) sẽ được đánh dấu là không phải là số nguyên tố.

Sau khi quá trình sàng nguyên tố kết thúc, vòng lặp thứ hai được sử dụng để duyệt qua tất cả các số từ 2 đến n và in ra những số có giá trị true trong mảng prime, tức là các số nguyên tố.