Để 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:
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ếua
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ủaa
, kiểm tra xema
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ủaa
, 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
đếni<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àmisPrime(i)
thì tăng giá trịsum
lêni
. - Nếu số nguyên
n
cũng là số nguyên tố, thì thêm giá trịn
vào tổngsum
. - Tăng giá trị
i
lên 1 và tiếp tục duyệt đến khii
bằngn
. - 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:
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:
- 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. - 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. - Input:
n = 1
Output:0
Giải thích: Không có số nguyên tố nhỏ hơn 1. - Input:
n = 2
Output:0
Giải thích: Không có số nguyên tố nhỏ hơn 2. - 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.
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 . Cảm ơn các bạn đã theo dõi trên ttnguyen.net
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