[C++] Tính tổng các số nguyên tố nhỏ hơn n

Để tính tổng các số nguyên tố nhỏ hơn n, chúng ta xây dựng hàm kiểm tra số nguyên tố. Sau đó, ta duyệt qua các phần tử và in ra kết quả là tổng các số nguyên tố nhỏ hơn n.

Xem thêm:

• Bài 29: kiểm tra số nguyên tố cùng nhau c++
• [C++] Sắp xếp các số nguyên tố về đầu dãy

1. Bài toán tính tổng các số nguyên tố nhỏ hơn n

Bài 30 (TH-CSLT-02): Viết hàm kiểm tra một số nguyên có phải là số nguyên tố hay không? Áp dụng tính tổng các số nguyên tố nhỏ hơn số n với n được nhập vào từ bàn phím.

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

Để giải quyết bài toán này, chúng ta có thể viết hai hàm. Hàm đầu tiên sẽ kiểm tra xem một số có phải là số nguyên tố hay không. Hàm thứ hai sẽ sử dụng hàm đầu tiên để tính tổng các số nguyên tố

2.1 Hàm kiểm tra số nguyên tố

Hàm isPrime() được dùng để kiểm tra xem một số nguyên a có phải là số nguyên tố hay không. Cách thức hoạt động của hàm như sau:

• Trường hợp a nhỏ hơn 2: nếu a là 0 hoặc 1 thì không phải là số nguyên tố, vì vậy hàm sẽ trả về giá trị false.
• Nếu a lớn hơn hoặc bằng 2, hàm sẽ duyệt từ 2 đến căn bậc hai của a, kiểm tra xem a có chia hết cho các số từ 2 đến căn bậc hai không. Nếu có, hàm sẽ trả về giá trị false, vì khi đó a không phải là số nguyên tố.
• Chúng ta chỉ kiểm tra đến căn bậc 2 của a vì nếu a có ước số nào lớn hơn căn bậc hai của a, thì ước số đó sẽ phải nhỏ hơn căn bậc hai của a.Ví dụ, để kiểm tra xem số nguyên dương a=37 có phải là số nguyên tố hay không, ta chỉ cần kiểm tra các ước số từ 2 đến căn bậc hai của 37, tức là từ 2 đến 6. Nếu không tìm thấy bất kỳ ước số nào của a trong khoảng này, ta có thể kết luận rằng 37 là số nguyên tố.
• Nếu hàm không trả về false trong vòng lặp, nghĩa là a không chia hết cho bất kỳ số nguyên nào từ 2 đến căn bậc hai của a, và do đó a là số nguyên tố. Hàm sẽ trả về giá trị true.

bool isPrime(int a) {
  if (a < 2) {
    return false;
  }
  for (int i = 2; i <= sqrt(a); i++) {
    if (a % i == 0) {
      return false;
    }
  }
  return true;
}

2.2 Hàm tính tổng các số nguyên tố nhỏ hơn n

Hàm sumPrime() là hàm tính tổng các số nguyên tố nhỏ hơn một số nguyên n được nhập từ bàn phím. Cách thức hoạt động của hàm như sau:

• Duyệt qua các số nguyên từ 2 đến i<n bằng vòng lặp while.
• Kiểm tra nếu số nguyên i là số nguyên tố bằng cách gọi hàm isPrime(i) thì tăng giá trị sum lên i.
• Nếu số nguyên n cũng là số nguyên tố, thì thêm giá trị n vào tổng sum.
• Tăng giá trị i lên 1 và tiếp tục duyệt đến khi i bằng n.
• Trả về giá trị tổng sum.

int sumPrime(int n) {
  int sum = 0, i = 2;
  while (i < n) {
    if (isPrime(i)) {
      sum += i;
    }
    if (isPrime(n)) {
      sum += n;
    }
    i++;
  }
  return sum;
}

Liên quan:

• [C++]Tính tổng các chữ số của một số nguyên dương N có CODE mẫu
• [C++]Tính tổng mảng C = A + B, in 3 mảng A, B, C ra màn hình

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

#include<iostream>
#include<math.h>
using namespace std;

//kiem tra so nguyen to
bool isPrime(int a){
    if(a<2){
        return false;
    }

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

    return true;
}

//Tinh tong cac so nguyen to nho hon n

int sumPrime(int n){
    int sum=0,i=2;
    while(i<n){
        if(isPrime(i)){
            sum+=i;
        }
        if(isPrime(n)){
            sum+=n;
        }
        i++;
    }
    return sum;
}

int main(){
    int n;
    cout<<"Nhap so nguyen n:"; cin>>n;
    cout<<"Tong cac so nguyen to nho hon n= "<<sumPrime(n);
}

4. Kết quả

Bộ test kiểm tra bài toán:

Bài tiếp theo: Bài 31: [C++]Tính tổng mảng C = A + B, in 3 mảng A, B, C ra màn hình