main

1.Thuật Toán Cơ Bản

Số nguyên tố là số nguyên dương có 2 ước là 1 và chính nó (1 không phải là số nguyên tố) ví dụ như : 2, 3, 5, 7, 11, 13, 19...

Để kiểm tra số N là nguyên tố bạn có thể tiếp cận theo cách đó là đi đếm ước của số đó, mình đã từng hướng dẫn cách đếm ước bằng cách duyệt tới √N. 

Bạn có thể xem lại tại tại đây nếu chưa rõ

Code : Kiểm tra số nguyên tố bằng cách đếm ước

#include "stdio.h"
#include "math.h"

int prime(int n){
    int dem = 0;
    for(int i = 1; i <= sqrt(n); i++){
        if(n % i == 0){
            ++dem;
            if(i != n / i){
                ++dem;
            }
        }
    }
    if(dem == 2){
        return 1; // true
    }
    else{
        return 0; // false;
    }
}

int main(){
    int n = 30;
    for(int i = 1; i <= n; i++){
        if(prime(i) == 1){
            printf("%d ", i);
        }
    }
    return 0;
}

Output : 

2 3 5 7 11 13 17 19 23 29

2. Phương pháp tối ưu

Trong phương pháp 1 thì code kiểm tra số nguyên tố luôn cần lặp √N vòng lặp. Bạn có thể cải tiến thuật toán bằng nhận xét sau : 

• Để xét tất cả các ước của N bạn chỉ cần duyệt từ 1 tới √N
• Nếu N có thêm 1 ước ngoài 1 và N thì có thể kết luận ngay N không phải là số nguyên tố
• Vậy ta sẽ bỏ qua không xét 2 ước là 1 và N mà chỉ xét các ước còn lại bằng cách duyệt từ 2 tới √N , khi gặp thêm ước của N có thể cho hàm trả về kết quả ngay thay vì phải lặp đủ √N vòng lặp

Code : 

#include "stdio.h"
#include "math.h"

int prime(int n){
    if(n < 2){
        return 0; // loại số âm, và 0, 1
    }
    for(int i = 2; i <= sqrt(n); i++){
        if(n % i == 0){
            return 0; // kết thúc ngay tại đây
        }
    }
    return 1; // là số nguyên tố
}

int main(){
    int n = 30;
    for(int i = 1; i <= n; i++){
        if(prime(i) == 1){
            printf("%d ", i);
        }
    }
    return 0;
}

Output :

2 3 5 7 11 13 17 19 23 29

Ví dụ với N = 60 sẽ có các cặp ước (1, 60), (2, 30), (3, 20), (4, 15), (5, 12) và (6, 10). Cặp (1, 60) bạn sẽ không xét vì chắc chắn nó cặp ước này rồi, giờ mình muốn chứng mình 60 không phải là số nguyên tố ta cần chỉ ra nó có thêm 1 ước nữa nhưng trong các cặp ước trên thì bạn chỉ cần lấy ước nhỏ hơn ra làm đại diện cho cặp ước đó thôi. 

Các ước đó là 2, 3, 4, 5, 6, mình đã từng chứng minh các ước này nhỏ hơn √N vì thế bạn chỉ cần duyệt từ 2 tới √N là đủ xét hết các ước đại diện cho các cặp ước của N.

Với N = 60 bạn thấy code trên chỉ thực hiện đúng 1 vòng lặp thay vì lặp đủ √60 vòng lặp như mục 1.

Chú ý : Trong code trên bạn cần kiểm tra các số < 2 và loại bỏ chúng, vì các số nhỏ hơn 2 thì vòng lặp for sẽ không thực hiện mà chạy xuống câu lệnh return 1 luôn nên có thể dẫn tới kết quả sai.

3. Một Số Bài Toán Với Số Nguyên Tố

Bài 1. Liệt kê và đếm các số nguyên tố từ 1 tới N

#include "stdio.h"
#include "math.h"

int prime(int n){
    if(n < 2){
        return 0; // loại số âm, và 0, 1
    }
    for(int i = 2; i <= sqrt(n); i++){
        if(n % i == 0){
            return 0; // kết thúc ngay tại đây
        }
    }
    return 1; // là số nguyên tố
}

int main(){
    int n = 30;
    int dem = 0;
    for(int i = 1; i <= n; i++){
        if(prime(i) == 1){
            printf("%d ", i);
            ++dem;
        }
    }
    printf("\n%d\n", dem);
    return 0;
}

Output : 

2 3 5 7 11 13 17 19 23 29 
10

Bài 2. Tìm số nguyên tố nhỏ nhất lơn hơn N

#include "stdio.h"
#include "math.h"

int prime(int n){
    if(n < 2){
        return 0; // loại số âm, và 0, 1
    }
    for(int i = 2; i <= sqrt(n); i++){
        if(n % i == 0){
            return 0; // kết thúc ngay tại đây
        }
    }
    return 1; // là số nguyên tố
}

int main(){
    int n = 32;
    while(1){
        if(prime(n) == 1){
            printf("%d\n", n);
            break;
        }
        ++n;
    }
    return 0;
}

Output : 

37

Bài 3. Liệt kê các số có tổng chữ số là số nguyên tố trong đoạn [1, N]

#include 
#include 

int prime(int n){
    if(n < 2){
        return 0; // loại số âm, và 0, 1
    }
    for(int i = 2; i <= sqrt(n); i++){
        if(n % i == 0){
            return 0; // kết thúc ngay tại đây
        }
    }
    return 1; // là số nguyên tố
}

int tong_nt(int n){
    int tong = 0;
    while(n){
        tong += n % 10;
        n /= 10;
    }
    return prime(tong); // ???
}

int main(){
    int n = 32;
    for(int i = 1; i <= n; i++){
        if(tong_nt(i) == 1){
            printf("%d ", i);
        }
    }
    return 0;
}

Output :

2 3 5 7 11 12 14 16 20 21 23 25 29 30 32

Bài 4. Liệt kê số thuần nguyên tố trong đoạn [1, N].

Số thuần nguyên tố thỏa mãn : 

• N là số nguyên tố
• N có tất cả các chữ số là số nguyên tố
• N có tổng chữ số là số nguyên tố 

Bạn cần viết 3 hàm : 1 hàm kiểm tra số nguyên tố, một hàm kiểm tra tất cả các chữ số của N là số nguyên tố và hàm kiểm tra tổng chữ số của N là số nguyên tố và kết hợp 3 hàm này lại với nhau.

#include "stdio.h"
#include "math.h"

int prime(int n){
    if(n < 2){
        return 0; 
    }
    for(int i = 2; i <= sqrt(n); i++){
        if(n % i == 0){
            return 0;
        }
    }
    return 1; 
}

int tong_nt(int n){
    int tong = 0;
    while(n){
        tong += n % 10;
        n /= 10;
    }
    return prime(tong); // ???
}

int chuso_nt(int n){
    while(n){
        int r = n % 10;
        if(r != 2 && r != 3 && r != 5 && r != 7){
            return 0;
        }
        n /= 10;
    }
    return 1;
}

int main(){
    int n = 500;
    for(int i = 1; i <= n; i++){
        if(tong_nt(i) && chuso_nt(i) && prime(i)){
            printf("%d ", i);
        }
    }
    return 0;
}

Output : 

2 3 5 7 23 223 227 337 353 373

Xem thêm bài giảng của mình về Số Nguyên Tố : 

WnvnjnDxxPs