HOME › lập trình c++ cơ bản dành cho người mới học lập trình>>17. mảng trong c++

Tìm số nguyên tố trong mảng C++

7 tháng 10 ,2021

Hướng dẫn cách tìm số nguyên tố trong mảng C++. Bạn sẽ học được cách tìm và liệt kê số nguyên tố trong mảng C++ để viết hàm in ra các số nguyên tố trong mảng C++, tách số nguyên tố trong mảng C++ cũng như là để sắp xếp các số nguyên tố trong mảng C++ sau bài học này.

Tìm và liệt kê số nguyên tố trong mảng C++ | In ra các số nguyên tố trong mảng C++

Để tìm số nguyên tố trong mảng C++, chúng ta sẽ lấy từng phần tử trong mảng ra và kiểm tra phần tử đó có phải là số nguyên tố hay không. Và nếu phần tử đó là số nguyên tố thì chúng ta sẽ liệt kê và in ra các số nguyên tố trong mảng C++.

Để kiểm tra một số trong mảng có phải là số nguyên tố hay không, chúng ta sẽ sử dụng tới hàm kiểm tra số nguyên tố trong C++ mà Kiyoshi đã giới thiệu trong bài dưới đây:

Xem thêm: Kiểm tra số nguyên tố trong C++

Với phương pháp tìm và liệt kê số nguyên tố trong mảng C++ như trên, chúng ta có thể viết hàm in ra các số nguyên tố trong mảng C++ trong chương trình như sau:

#include <iostream>
using namespace std;

/*Tạo macro SIZE_OF_ARRAY để lấy độ dài (số phần tử) của mảng chỉ định*/
#define SIZE_OF_ARRAY(array)  (sizeof(array)/sizeof(array[0]))

/*Tạo hàm kiểm tra số nguyên tố trong C++*/
int check_prime_number(int n){
    //flag = 0 => không phải số nguyên tố
    //flag = 1 => số nguyên tố
    
    int flag = 1;

    if (n <2) return flag = 0; /*Số nhỏ hơn 2 không phải số nguyên tố => trả về 0*/
    
    /*Sử dụng vòng lặp while để kiểm tra có tồn tại ước số nào khác không*/
    int i = 2;
    while(i <n){
        if( n%i==0 ) {
            flag = 0;
            break; /*Chỉ cần tìm thấy 1 ước số là đủ và thoát vòng lặp*/
        }
        i++;
    }

    return flag;
}

/*Tạo hàm in ra các số nguyên tố trong mảng C++*/
void show_prime_number_from_array(int array[], int length){
    int prime_number[100];

    for (int i = 0; i < length; i++){
      //Kiểm tra phần tử là số nguyên tố hay không
      //Nếu là số nguyên tố thì in ra màn hình     
      if (check_prime_number(array[i]) == 1)  cout << array[i] <<' ';
    }
    
}
int main(){
    //Khởi tạo mảng in ra các số nguyên tố
    int array[] = {0,1,2,3,4,5,6,7,8,9,10};

    //in ra các số nguyên tố trong mảng C++ bằng hàm đã tạo
    show_prime_number_from_array(array,SIZE_OF_ARRAY(array));

    return 0;
}

Kết quả của chương trình viết hàm in ra các số nguyên tố trong mảng C++ như sau:

2 3 5 7

Tách số nguyên tố trong mảng C++

Để tách số nguyên tố trong mảng C++ thì ngoài việc tìm và liệt kê các số nguyên tố ra, thì chúng ta cũng cần phải chuẩn bị sẵn một mảng chứa kết quả là các số nguyên tố đã được tìm thấy trong mảng.

Tương tự như trên thì để kiểm tra một số trong mảng có phải là số nguyên tố hay không, chúng ta cũng sẽ sử dụng tới hàm kiểm tra số nguyên tố trong C++ mà Kiyoshi đã giới thiệu trong bài dưới đây:

Xem thêm: Kiểm tra số nguyên tố trong C++

Và chúng ta viết chương trình tách số nguyên tố trong mảng C++ như sau:

#include <iostream>
using namespace std;

/*Tạo macro SIZE_OF_ARRAY để lấy độ dài (số phần tử) của mảng chỉ định*/
#define SIZE_OF_ARRAY(array)  (sizeof(array)/sizeof(array[0]))

/*Tạo hàm in phần tử trong mảng*/
void show_array(int array[], int length){
    for(short i = 0; i < length; i++)  cout << array[i] <<' ';   
    cout << endl;
}

/*Tạo hàm kiểm tra số nguyên tố trong C++*/
int check_prime_number(int n){
    //flag = 0 => không phải số nguyên tố
    //flag = 1 => số nguyên tố
    
    int flag = 1;

    if (n <2) return flag = 0; /*Số nhỏ hơn 2 không phải số nguyên tố => trả về 0*/
    
    /*Sử dụng vòng lặp while để kiểm tra có tồn tại ước số nào khác không*/
    int i = 2;
    while(i <n){
        if( n%i==0 ) {
            flag = 0;
            break; /*Chỉ cần tìm thấy 1 ước số là đủ và thoát vòng lặp*/
        }
        i++;
    }

    return flag;
}

int main(){
    //Khai báo mảng chứa kết quả
    int prime_number_array[100];

    //Khởi tạo mảng tách ra các số nguyên tố
    int array[] = {0,7,2,3,6,5};

    //Sử dụng macro ở trên để lấy độ dài mảng
    int length = SIZE_OF_ARRAY(array);

    int prime_number_count = 0;
    for (int i = 0; i < length; i++){
        //Kiểm tra phần tử là số âm hay dương
        //Và gán số tìm thấy vào các mảng âm dương tương ứng
        //Cũng như tăng dần số phần tử trong mảng kết quả
        if (check_prime_number(array[i]) == 1) {
          prime_number_array[prime_number_count]=array[i];
          ++ prime_number_count;
        } 
    }

    //In ra mảng số nguyên tố đã tách ra
    show_array(prime_number_array, prime_number_count);

    return 0;
}

Kết quả của chương trình tách số nguyên tố trong mảng C++ như sau:

7 2 3 5

Sắp xếp các số nguyên tố trong mảng C++

Ở phần trên chúng ta đã biết cách tách hoặc in ra các số nguyên tố trong mảng C++ rồi. Tuy nhiên thứ tự tách cũng như in ra của các số nguyên tố đó sẽ giống với thứ tự của chúng trong mảng ban đầu.

Để có thể sắp xếp các số nguyên tố tố và in ra màn hình, chúng ta sẽ cần phải thêm một xử lý nữa, đó là xử lý sắp xếp mảng trong C++ mà Kiyoshi đã hướng dẫn chi tiết tại bài:

Xem thêm: Sắp xếp mảng trong C++

Ở đây, chúng ta sẽ có 2 cách, đó là sắp xếp mảng ban đầu trước, rồi sau đó mới tiến hành tách và in ra các số nguyên tố trong mảng đó, hoặc là tiến hành tách số nguyên tố trong mảng trước, rồi mới đem kết quả đi sắp xếp theo thứ tự tăng dần hoặc giảm dần.

Do cách thứ nhất sẽ khiến mảng ban đầu bị thay đổi, nên sau đây Kiyoshi sẽ trình bày cách thứ 2, đó là sắp xếp kết quả của phép tách số nguyên tố từ mảng.

Và chúng ta sẽ thêm xử lý này vào chương trình tách số nguyên tố trong mảng C++ ở trên như sau:

#include <iostream>
#include <cstdlib>
using namespace std;

/*Tạo macro SIZE_OF_ARRAY để lấy độ dài (số phần tử) của mảng chỉ định*/
#define SIZE_OF_ARRAY(array)  (sizeof(array)/sizeof(array[0]))

/*Tạo hàm in phần tử trong mảng*/
void show_array(int array[], int length){
    for(short i = 0; i < length; i++)  cout << array[i] <<' ';   
    cout << endl;
}

/*Tạo hàm so sánh giảm dần sử dụng trong hàm sắp xếp qsort*/
int compareIntDesc(const void* a, const void* b){
    int aNum = *(int*)a;
    int bNum = *(int*)b;

    return bNum - aNum;
}

/*Tạo hàm so sánh tăng dần sử dụng trong hàm qsort*/
int compareIntAsc(const void* a, const void* b){
    int aNum = *(int*)a;
    int bNum = *(int*)b;

    return aNum - bNum;
}

/*Tạo hàm kiểm tra số nguyên tố trong C++*/
int check_prime_number(int n){
    //flag = 0 => không phải số nguyên tố
    //flag = 1 => số nguyên tố
    
    int flag = 1;

    if (n <2) return flag = 0; /*Số nhỏ hơn 2 không phải số nguyên tố => trả về 0*/
    
    /*Sử dụng vòng lặp while để kiểm tra có tồn tại ước số nào khác không*/
    int i = 2;
    while(i <n){
        if( n%i==0 ) {
            flag = 0;
            break; /*Chỉ cần tìm thấy 1 ước số là đủ và thoát vòng lặp*/
        }
        i++;
    }

    return flag;
}

int main(){
    //Khai báo mảng chứa kết quả
    int prime_number_array[100];

    //Khởi tạo mảng tách ra các số nguyên tố
    int array[] = {0,7,2,3,6,5};

    //Sử dụng macro ở trên để lấy độ dài mảng
    int length = SIZE_OF_ARRAY(array);

    int prime_number_count = 0;
    for (int i = 0; i < length; i++){
        //Kiểm tra phần tử là số âm hay dương
        //Và gán số tìm thấy vào các mảng âm dương tương ứng
        //Cũng như tăng dần số phần tử trong mảng kết quả
        if (check_prime_number(array[i]) == 1) {
          prime_number_array[prime_number_count]=array[i];
          ++ prime_number_count;
        } 
    }

    //In ra mảng số nguyên tố đã tách ra
    cout << "Cac so nguyen to: ";
    show_array(prime_number_array, prime_number_count);

    //Sắp xếp các số nguyên tố theo thứ tự tăng dần bằng hàm qsort
    qsort(prime_number_array, prime_number_count, sizeof(int), compareIntAsc);
    cout << "Sap xep tang dan: ";
    show_array(prime_number_array, prime_number_count);

    //Sắp xếp các số nguyên tố theo thứ tự giảm dần bằng hàm qsort
    qsort(prime_number_array, prime_number_count, sizeof(int), compareIntDesc);
    cout << "Sap xep giam dan: ";
    show_array(prime_number_array, prime_number_count);

    return 0;
}

Kết quả của chương trình sắp xếp các số nguyên tố trong mảng C++ như sau:

Cac so nguyen to: 7 2 3 5 
Sap xep tang dan: 2 3 5 7 
Sap xep giam dan: 7 5 3 2

Tổng kết

Trên đây Kiyoshi đã hướng dẫn bạn cách tìm số nguyên tố trong mảng C++ rồi. Để nắm rõ nội dung bài học hơn, bạn hãy thực hành viết lại các ví dụ của ngày hôm nay nhé.

Và hãy cùng tìm hiểu những kiến thức sâu hơn về C++ trong các bài học tiếp theo.