C++での一意の素因数の最大数

与えられたタスクは、Nが与えられた[1、N]の範囲で数が持つことができる一意の素因数の最大数を見つけることです。

例を使用して、私たちがしなければならないことを理解しましょう-

入力 − n =100

出力 − 3

説明 − [1、100]

30 =3 * 2 *5=固有の素因数。したがって、[1、100]の範囲で、最大3つの固有の因子を見つけることができます。

入力 − n =300

出力 − 4

以下のプログラムで使用されるアプローチは次のとおりです

• 関数MaxPrime（）では、最初に（N <2）かどうかをチェックします。その場合は単にゼロを返し、そうでない場合は続行します。

• 次に、エラトステネスのふるいを使用して、指定された数Nの前にあるすべての素数を見つけます。

• int型の2つの変数pro=1とmax=0を初期化して、それぞれ製品と最終回答を格納します。

• エラトステネスのふるいの中で、-pro =* p;

  と書くことにより、積がNより小さくなるまで、素数の最初のセットを乗算します。

• （pro> N）かどうかを確認します。その場合は、最大値を返し、最大値に1を加算します。

• ふるいの外でも、最大値を返します。

例

#include <bits/stdc++.h>
using namespace std;
int MaxPrime(int N){
   if (N < 2)
      return 0;
   // Using Sieve of Eratosthenes
   bool Arr[N+1];
   memset(Arr, true, sizeof(Arr));
   int pro = 1, max = 0;
   for (int p=2; p*p<=N; p++){
      if (Arr[p] == true){
         for (int i=p*2; i<=N; i += p)
            Arr[i] = false;
         /*Multiply first set of prime numbers while product remains smaller than N*/
         pro *= p;
         if (pro > N)
            return max;
         max++;
      }
   }
   return max;
}
//Main function
int main(){
   int N = 300;
   cout << MaxPrime(N);
   return 0;
}

出力

上記のコードを実行すると、次の出力が得られます-

4