C++で1からnまでの素数の合計を見つけるプログラム

この問題では、数nが与えられます。私たちのタスクは、C++で1からnまでの素数の合計を見つけるプログラムを作成することです 。

素数は、2つの要素しかない数です。それらは数と1です。

問題を理解するために例を見てみましょう

入力

n = 15

出力

41

説明

1から15までの素数は2、3、5、7、11、13です。sumis41。

ソリューションアプローチ

この問題を解決する簡単な方法は、ループを使用して、各数値が素数であるかどうかを確認し、素数であるすべての数値を追加することです。

数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

効果的な解決策は、エラトステネスのふるいを使用して素数を見つけ、それらを加算して必要な合計を見つけることです。

ソリューションの動作を説明するプログラム

例

#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