Bất kỳ số nguyên nào lớn hơn 1 và chỉ có hai thừa số là 1 và chính số đó, được gọi là số nguyên tố. Ngoài hai số này, nó không có ước số dương. Ví dụ:7 =1 × 7
Sau đây là thuật toán để tìm xem một số có phải là số nguyên tố hay không -
-
Lấy biến số nguyên A.
-
Chia biến A với (A-1 cho 2).
-
Nếu A chia hết cho bất kỳ giá trị nào (A-1 đến 2) thì nó không phải là số nguyên tố.
-
Nếu không, nó là nguyên tố.
Ví dụ
Chương trình Java sau đây chấp nhận một số nguyên từ người dùng, tìm xem số đã cho có phải là số nguyên tố hay không và in ra số nguyên tố tiếp theo.
import java.util.Scanner;
public class NextNumberisPrime {
public static int isPrime(int num){
int prime = 1;
for(int i = 2; i < num; i++) {
if((num % i) == 0) {
prime = 0;
}
}
return num;
}
public static int nextPrime(int num) {
num++;
for (int i = 2; i < num; i++) {
if(num%i == 0) {
num++;
i=2;
} else {
continue;
}
}
return num;
}
public static void main(String args[]){
Scanner sc = new Scanner(System.in);
System.out.println("Enter a number ::");
int num = sc.nextInt();
int result = 0;
int prime = isPrime(num);
if (prime == 1) {
System.out.println(num+" is a prime number");
} else {
System.out.println(num+" is not a prime number");
}
System.out.println("Next prime number is: "+nextPrime(num));
}
} Đầu ra
Enter a number :: 25 25 is not a prime number Next prime number is: 29