Viết chương trình liệt kê tất cả các số nguyên tố nhỏ hơn n

Đề bài viết chương trình liệt kê các số nguyên tố nhỏ hơn n, để làm được bài này các bạn nên sử dụng thuật toán kiểm tra nguyên tố, hôm nay tienanhvn sẽ trình bày cho các bạn về thuật toán kiểm tra nguyên tố và thực hiện chương trình liệt kê số nguyên tố.

Tôi sẽ không nói về nguyên tố là gì nữa, định nghĩa nguyên tố như thế nào nữa các bạn có thể tham khảo số nguyên tố là gì tại đây.

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

Nhâp n = 54

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

1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53

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

1.    Thực hiện kiểm tra số nguyên tố
2.    Thực hiện một vòng lặp từ [2;n]
3.    Kiểm tra nếu là số nguyên tố thì in ra

Để tìm hiểu thuật toán kiểm tra số nguyên tố bạn có thể xem tại đây.

Thực hiện chương trình.

   Viế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;
}

   viết hàm liệt kê ra các số nguyên tố nhỏ hơn nay

   void inputNguyenTo(int n){
for(int i = 1 ;i<n;i++){
if(checkNguyenTo(i)){
System.out.print(" " +i);
}
}
}

   Khai báo hàm main

   public static void main(String args[]){
Scanner sc = new Scanner(System.in);
Lietkesonguyento lk = new Lietkesonguyento();
int n =28;
System.out.println("Nhap n = \n");
n = sc.nextInt();
lk.inputNguyenTo(n);
}

Toàn bộ chương trình liệt kê số nguyên tố.

package baitap3;
import java.util.Scanner;
public class Lietkesonguyento {
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 inputNguyenTo(int n){
for(int i = 1 ;i<n;i++){
if(checkNguyenTo(i)){
System.out.print(" " +i);
}
}
}
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
Lietkesonguyento lk = new Lietkesonguyento();
int n =28;
System.out.println("Nhap n = \n");
n = sc.nextInt();
lk.inputNguyenTo(n);
}
}