prime number là gì

1. Như thế nào là là một trong những yếu tố (prime number)?

Một số vẹn toàn dương chỉ phân chia không còn cho một và chủ yếu nó được gọi là số yếu tố. Ví dụ, 2, 3, 5, 7, 11, 13, 17, 19, 23,… là những số yếu tố. Lưu ý: 0 và 1 ko nên là số yếu tố.

Ý tưởng đánh giá một trong những vẹn toàn dương n liệu có phải là số yếu tố hoặc không?

Bạn đang xem: prime number là gì

1. Nếu số vẹn toàn dương n là 0 hoặc 1 thì tóm lại ko nên là số yếu tố.

2. Nếu n không phân chia hết mang đến ngẫu nhiên số nào là kể từ 2 cho tới n-1 thì tóm lại n là số yếu tố. trái lại, tóm lại n ko nên là số yếu tố.

Dễ thấy, chỉ mất số 2 là số yếu tố chẵn, toàn bộ những số chẵn không giống ko nên là số yếu tố vì thế bọn chúng phân chia không còn mang đến 2. Do bại liệt, chứ không nên duyệt kể từ 2 cho tới n-1, tất cả chúng ta hoàn toàn có thể chỉ đánh giá kể từ 2 cho tới n/2.

Xem thêm: Mách bạn những mẫu giày Converse thời trang và cá tính

Ngoài ra, người tớ đang được minh chứng được rằng: chỉ cần thiết đánh giá coi n với phân chia không còn mang đến ngẫu nhiên số nào là kể từ 2 cho tới căn bậc nhị của n nhằm xác lập coi n với nên số yếu tố hay là không.

2. Chương trình đánh giá số yếu tố vô Java

Sử dụng vòng lặp for vô Java nhằm đánh giá n với phân chia không còn mang đến ngẫu nhiên số nào là kể từ 2 cho tới n-1 hoặc không?

Xem thêm: bói bài tarot về tiền bạc hôm nay

package primenumber;
import java.util.Scanner;

public class PrimeNumber {
    public static void main(String[] args) {
        int num;
        boolean is_prime = true;
        System.out.print("Enter a positive integer: ");
        try (Scanner scanner = new Scanner(System.in)) {
            num = scanner.nextInt();
        }
        // 0 and 1 are not prime numbers
        if (num == 0 || num == 1) {
            is_prime = false;
        }
        // loop vĩ đại kiểm tra if n is prime
        for (int i = 2; i <= num-1; i++) {
            if (num % i == 0) {
                is_prime = false;
                break;
            }
        }
        if (is_prime) {
            System.out.print(num + " is a prime number");
        } else {
            System.out.print(num + " is not a prime number");
        }
    }
}

Chúng tớ hoàn toàn có thể thay cho thay đổi ĐK lặp vô for nhằm chỉ chạy kể từ 2 cho tới n/2.

// loop vĩ đại kiểm tra if n is prime
for (int i = 2; i <= num/2; i++) {
    if (num % i == 0) {
        is_prime = false;
        break;
    }
}

Chúng tớ hoàn toàn có thể thay cho thay đổi ĐK lặp vô for nhằm chỉ chạy kể từ 2 cho tới căn bậc 2 của n (Math.sqrt(n)).

// loop vĩ đại kiểm tra if n is prime
for (int i = 2; i <= Math.sqrt(num); i++) {
    if (num % i == 0) {
        is_prime = false;
        break;
    }
}

Chúng tớ nên làm duyệt cho tới căn bậc 2 của n nhằm thực hiện ngắn ngủn gọn gàng số phen lặp vô for.