[C]. Số Nguyên Tố

Trong bài học kinh nghiệm này những các bạn sẽ lần hiểu về số Nguyên Tố, một kỹ năng vô cùng cần thiết nhập toán học tập và tin yêu học

NỘI DUNG :

Thuật Toán Cơ Bản
Thuật Toán Tối Ưu
Một Số Bài Toán Với Số Nguyên Tố
Video Tutorial

main

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

Số yếu tắc là số nguyên vẹn dương đem 2 ước là 1 trong những và chủ yếu nó (1 ko nên là số nguyên vẹn tố) ví như : 2, 3, 5, 7, 11, 13, 19...

Để đánh giá số N là yếu tắc chúng ta có thể tiếp cận Theo phong cách này là lên đường kiểm đếm ước của số cơ, tôi đã từng chỉ dẫn cơ hội kiểm đếm ước bằng phương pháp duyệt cho tới √N.

Bạn rất có thể xem xét lại tại tại đây nếu như ko rõ

Code : Kiểm tra số yếu tắc bằng phương pháp kiểm đế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; 
    }
    else{
        return 0; 
    }
}

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 cách thức 1 thì code đánh giá số yếu tắc luôn luôn cần thiết lặp √N vòng lặp. quý khách hàng rất có thể nâng cấp thuật toán vày đánh giá sau :

Để xét toàn bộ những ước của N chúng ta chỉ việc duyệt từ là 1 cho tới √N
Nếu N đem thêm một ước ngoài 1 và N thì rất có thể Tóm lại tức thì N ko nên là số nguyên vẹn tố
Vậy tớ tiếp tục bỏ dở ko xét 2 ước là 1 trong những và N nhưng mà chỉ xét những ước còn sót lại bằng phương pháp duyệt kể từ 2 cho tới √N , Khi bắt gặp thêm thắt ước của N rất có thể mang đến hàm trả về thành phẩm tức thì thay cho nên lặp đầy đủ √N vòng lặp

Code :

#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 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 những cặp ước (1, 60), (2, 30), (3, 20), (4, 15), (5, 12) và (6, 10). Cặp (1, 60) các bạn sẽ ko xét vì thế chắc chắn là nó cặp ước này rồi, giờ mình đang có nhu cầu muốn triệu chứng bản thân 60 ko nên là số yếu tắc tớ cần thiết chỉ ra rằng nó đem thêm một ước nữa tuy nhiên trong số cặp ước bên trên thì chúng ta chỉ việc lấy ước nhỏ rộng lớn đi ra thực hiện đại diện thay mặt mang đến cặp ước cơ thôi.

Các ước này là 2, 3, 4, 5, 6, tôi đã từng minh chứng những ước này nhỏ rộng lớn √N vì vậy chúng ta chỉ việc duyệt kể từ 2 cho tới √N là đầy đủ xét không còn những ước đại diện thay mặt cho những cặp ước của N.

Với N = 60 chúng ta thấy code bên trên chỉ triển khai chính 1 vòng lặp thay cho lặp đầy đủ √60 vòng lặp như mục 1.

Chú ý : Trong code bên trên bạn phải đánh giá những số < 2 và vô hiệu bọn chúng, vì thế những số nhỏ rộng lớn 2 thì vòng lặp for sẽ không còn triển khai nhưng mà chạy xuống câu mệnh lệnh return 1 luôn luôn nên rất có thể dẫn cho tới thành phẩm sai.

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

Bài 1. Liệt kê và kiểm đếm những số yếu tắc từ là 1 cho tới N

#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 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ố yếu tắc nhỏ nhất lơn rộng lớn N

#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 main(){
    int n = 32;
    while(1){
        if(prime(n) == 1){
            printf("%d\n", n);
            break;
        }
        ++n;
    }
    return 0;
}

Output :

Bài 3. Liệt kê những số đem tổng chữ số là số yếu tắc trong khúc [1, N]

#include 
#include 

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 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 yếu tắc trong khúc [1, N].

Số thuần yếu tắc thỏa mãn nhu cầu :

N là số nguyên vẹn tố
N đem toàn bộ những chữ số là số nguyên vẹn tố
N đem tổng chữ số là số nguyên vẹn tố

Bạn cần thiết ghi chép 3 hàm : 1 hàm đánh giá số yếu tắc, một hàm đánh giá toàn bộ những chữ số của N là số yếu tắc và hàm đánh giá tổng chữ số của N là số yếu tắc và phối kết hợp 3 hàm đó lại cùng 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 thắt bài bác giảng của tôi về Số Nguyên Tố :

WnvnjnDxxPs