[C++] Tính tổng các số nguyên tố nhỏ hơn n và sắp xếp

1. Input: n = 10 Output: 17 Giải thích: Các số nguyên tố nhỏ hơn 10 là 2, 3, 5, 7. Tổng của chúng là 2 + 3 + 5 + 7 = 17.
2. Input: n = 20 Output: 77 Giải thích: Các số nguyên tố nhỏ hơn 20 là 2, 3, 5, 7, 11, 13, 17, 19. Tổng của chúng là 2 + 3 + 5 + 7 + 11 + 13 + 17 + 19 = 77.
3. Input: n = 1 Output: 0 Giải thích: Không có số nguyên tố nhỏ hơn 1.
4. Input: n = 2 Output: 0 Giải thích: Không có số nguyên tố nhỏ hơn 2.
5. Input: n = 100 Output: 1060 Giải thích: Các số nguyên tố nhỏ hơn 100 là 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97. Tổng của chúng là 1060.

2. Sắp xếp các số nguyên tố về đầu dãy

Bài 18: Nhập vào từ bàn phím dãy số gồm n số nguyên (n>0) và thực hiện các yêu cầu sau đây:

1. Hiển thị dãy số ra màn hình.
2. Nhập vào từ bàn phím số nguyên x. Hãy cho biết x xuất hiện trong dãy số bao nhiêu lần và các vị trí xuất hiện của x.
3. Xoá các số có giá trị bằng 0 có trong dãy.
4. Sắp xếp các số nguyên tố về đầu dãy, các số không phải là số nguyên tố về cuối dãy.
5. Tính trung bình cộng các số chia hết cho 3 có trong dãy.

2.1. Ý tưởng thuật toán

– Có nhiều phương pháp để đưa các số nguyên tố về đầu dãy, dưới đây mình sẽ gợi ý cách tách thành 2 mảng theo các bước sau:

• Xây dựng hàm kiểm tra số nguyên tố
• Duyệt mảng, nếu là số nguyên tố thì gán vào mảng b ngược lại gán vào mảng c
• Gộp mảng c vào mảng b và xuất mảng màn hình

Liên quan: tách mảng c++

Ví dụ mã nguồn:

void sapxepsonguyento(int n, int a[]){

    int b[255], c[255],m=0,k=0;
    //tachmang
    for(int i=0;i<n;i++){
        if(isPrime(a[i])){
            m++;
            b[m]=a[i];
        }else{
            k++;
            c[k]=a[i];
        }
    }
    //Gop mang
    for(int i=m+1;i<=n;i++){
        b[i]=c[i-m];
    }

    for(int i=1;i<=n;i++){
        cout<<setw(5)<<b[i];
    }
}

2.2. Cài đặt chương trình

Mã nguồn hoàn chỉnh:

#include <iostream>
#include <iomanip>
#include <math.h>

using namespace std;

//kiem tra so nguyen to
bool isPrime(int p){

        if(p<=1) return false;
        for(int i=2;i<=sqrt(p); i++){
            if(p%i==0){
                return false;
            }
        }
        return true;
    }

//nhap mang
void nhapmang(int n,int a[]){

    for(int i=0;i<n;i++){
        cout<<"a["<<i<<"]= ";
        cin>>a[i];
    }
}

//xuat mang
void xuatmang(int n, int a[]){
    for(int i=0;i<n;i++){
        cout<<setw(5)<<a[i];
    }
}


//Nhập vào từ bàn phím số nguyên x. Hãy cho biết x xuất hiện trong dãy số bao nhiêu lần và các vị trí xuất hiện của x
void timx(int n, int a[]){

    int x,dem;
    cout<<"Nhap so nguyen x: "; cin>>x;
    for(int i=0;i<n;i++){
        if(a[i]==x){
            dem++;
            cout<<" Phan tu "<<x<<" xuat hien vi tri "<<i+1<<endl;
        }
    }

    if(dem!=0){
        cout<<"Phan tu "<<x<<" xuat hien "<<dem<<" lan";
    }else{
        cout<<"Khong co phan tu nao bang x";
    }
}


void Xoacacsocogiatribang0(int n, int a[]){
    int j=0;
    for(int i=0;i<n;i++){
        if(a[i]!=0){
            a[j]=a[i];
            j++;
        }
    }

    for(int i=0;i<j;i++){
        cout<<setw(5)<<a[i];
    }
}

//Sắp xếp các số nguyên tố về đầu dãy, các số không phải là số nguyên tố về cuối dãy
void sapxepsonguyento(int n, int a[]){

    int b[255], c[255],m=0,k=0;

    for(int i=0;i<n;i++){
        if(isPrime(a[i])){
            m++;
            b[m]=a[i];
        }else{
            k++;
            c[k]=a[i];
        }
    }

    for(int i=m+1;i<=n;i++){
        b[i]=c[i-m];
    }

    for(int i=1;i<=n;i++){
        cout<<setw(5)<<b[i];
    }
}

//Tính trung bình cộng các số chia hết cho 3 có trong dãy
void trungbinhcong(int n, int a[]){

    int sum=0,d=0;
    for(int i=0;i<n;i++){
        if(a[i]%3==0){
            sum+=a[i];
            d++;
        }
    }

    if(sum==0){
        cout<<"khong co so nao chia het cho 3"<<endl;
    }else{
        cout<<"Trung binh cac so chia het cho 3 = "<<sum/d;
    }
}
int main(){

    int i, n, chon, x, a[255];

    do{
        cout<<"1. Nhap mang"<<endl;
        cout<<"2. Xuat mang"<<endl;
        cout<<"3. Cho biet x xuat hien bao nhieu lan"<<endl;
        cout<<"4. Sap xep so nguyen to ve dau day"<<endl;
        cout<<"5. Tinh trung binh cong cac so chia het cho 3"<<endl;
        cout<<"6. Xoa cac so co gia tri bang 0 trong day"<<endl;
        cout<<"Lua chon: "; cin>>chon;

        switch(chon){
            case 1:{
                cout<<"Nhap so phan tu: "; cin>>n;
                nhapmang(n,a);
                cout<<endl;
                break;
            }
            case 2:{
                xuatmang(n,a);
                 cout<<endl;
                break;
            }
            case 3:{
                timx(n,a);
                cout<<endl;
                break;
            }
            case 4:{
                sapxepsonguyento(n,a);
                cout<<endl;
                break;
            }
            case 5:{
                trungbinhcong(n,a);
                cout<<endl;
                break;
            }
            case 6:{
                Xoacacsocogiatribang0(n,a);
                cout<<endl;
                break;
            }

            default: exit(0);
        }
    }while(chon!=0);

}

2.3 Kết quả chạy chương trình

Trên đây là đoạn mã đơn giản và thuật toán tính tổng các số nguyên tố nhỏ hơn n và sắp xếp . Cảm ơn các bạn đã theo dõi trên ttnguyen.net

Tải full bài tập thực hành C/C++ có lời giải:

Bài viết cùng chủ đề:

thuật toán prim

file nhị phân c++

xoá phần tử trong mảng c++

viết chương trình nhập vào tọa độ 2 điểm