โปรแกรมหาผลรวมของจำนวนเฉพาะระหว่าง 1 ถึง n ใน C++

ในปัญหานี้ เราได้รับตัวเลข n งานของเราคือสร้าง โปรแกรมเพื่อค้นหาผลรวมของจำนวนเฉพาะระหว่าง 1 ถึง n ใน C++ .

Prime Numbers คือตัวเลขที่มีตัวประกอบเพียงสองตัว คือตัวเลขและ 1.

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

n = 15

ผลลัพธ์

41

คำอธิบาย

จำนวนเฉพาะระหว่าง 1 ถึง 15 คือ 2, 3, 5, 7, 11, 13 ผลรวม 41

แนวทางการแก้ปัญหา

วิธีง่ายๆ ในการแก้ปัญหาคือการใช้ลูปและตรวจสอบว่าแต่ละจำนวนเป็นจำนวนเฉพาะหรือไม่ แล้วบวกทั้งหมดที่เป็นจำนวนเฉพาะ

ตรวจสอบว่าจำนวน i เป็นจำนวนเฉพาะหรือไม่ เราจะวนจาก i ถึง i/2 ตรวจสอบว่ามีตัวเลขที่สามารถหาร i ได้หรือไม่ ถ้าใช่ แสดงว่าจำนวนนั้นไม่ใช่จำนวนเฉพาะ

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#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;
}

ผลลัพธ์

The sum of prime number between 1 to 15 is 45

วิธีแก้ปัญหาที่มีประสิทธิภาพคือการใช้ Sieve of Eratosthenes เพื่อค้นหาจำนวนเฉพาะและเพิ่มเข้าไปเพื่อค้นหาผลรวมที่ต้องการ

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

ตัวอย่าง

#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;
}

ผลลัพธ์

The sum of prime number between 1 to 15 is 41