Trong bài toán này, chúng ta được cho một số n. Nhiệm vụ của chúng tôi là tạo một chương trình tìm tổng các số nguyên tố từ 1 đến n trong C ++ .
Số nguyên tố là những số chỉ có hai yếu tố. Chúng là số và 1.
Hãy lấy một ví dụ để hiểu vấn đề
Đầu vào
n = 15
Đầu ra
41
Giải thích
Các số nguyên tố từ 1 đến 15 là 2, 3, 5, 7, 11, 13. Tổng là 41.
Phương pháp tiếp cận giải pháp
Một cách đơn giản để giải quyết vấn đề là sử dụng một vòng lặp và kiểm tra xem mỗi số có phải là số nguyên tố hay không và thêm tất cả những số đó là số nguyên tố.
Để kiểm tra xem một số i có phải là số nguyên tố hay không. Chúng tôi sẽ lặp lại từ i đến i / 2. kiểm tra nếu có một số có thể chia i. Nếu có, thì số không phải là số nguyên.
Chương trình minh họa hoạt động của giải pháp của chúng tôi
Ví dụ
#include <iostream>
using namespace std;
bool isPrime(int n){
for(int i = 2; i < n/2; i++){
if(n%i == 0){
return false;
}
}
return true;
}
int findPrimeSum(int n){
int sumVal = 0;
for(float i = 2; i <= n; i++){
if(isPrime(i))
sumVal += i;
}
return sumVal;
}
int main(){
int n = 15;
cout<<"The sum of prime number between 1 to "<<n<<" is "<<findPrimeSum(n);
return 0;
} Đầu ra
The sum of prime number between 1 to 15 is 45
Một giải pháp hiệu quả là sử dụng Sieve of Eratosthenes để tìm các số nguyên tố và cộng chúng để tìm tổng cần thiết.
Chương trình minh họa hoạt động của giải pháp của chúng tôi
Ví dụ
#include <iostream>
using namespace std;
int findPrimeSum(int n){
int arr[n+1] = {0};
for (int i = 2; i < n; i++) {
for (int j = i * i; j < n; j+=i) {
arr[j - 1] = 1;
}
}
int sumVal;
for (int i = 2; i < n; i++) {
if (arr[i - 1] == 0)
sumVal += i;
}
return sumVal;
}
int main(){
int n = 15;
cout<<"The sum of prime number between 1 to "<<n<<" is "<<findPrimeSum(n);
return 0;
} Đầu ra
The sum of prime number between 1 to 15 is 41