C++で最大Nまでのログを計算するために必要なログ値の最小数を見つけます

log（x * y）=log（x）+ log（y）であることがわかっています。したがって、1からNまでのすべてのログ値を計算するために必要なログ値の最小数を確認します。したがって、Nが6の場合、log（1）からlog（6）のように、出力は3になります。 log（1）を除いて、3つのログ値が必要です。 log（1）は常に0であるため、無視します。ここで、log（2）とlog（3）について、を見つける必要があります。その後、log（4）の場合はlog（2）+ log（2）になりますが、log（2）の値がわかっているため、これを再度計算することはありません。log（5）の場合は計算する必要があります。つまり、カウントは3、log（6）=log（3）+ log（2）であり、すでにわかっているので、カウントは3です。

この問題は、1からNの範囲の素数を見つけるために減らすことができます。素数の場合、ログ値を個別に計算する必要があることがわかります。それ以外の場合は、因数分解して計算する必要があります。

例

#include<iostream>
#include<vector>
#define MAX 1000005
using namespace std;
vector<int> prime(MAX, 1);
void seive(int N) {
   prime[0] = prime[1] = 0;
   for (int i = 2; i <= N; i++) {
      if (prime[i] == 1) {
         for (int j = 2; i * j <= N; j++)
         prime[i * j] = 0;
      }
   }
}
int numberOfLogs(int N) {
   int log_count = 0;
   seive(N);
   for (int i = 1; i <= N; i++) {
      if (prime[i] == 1)
      log_count++;
   }
   return log_count;
}
int main() {
   int N = 8;
   cout<<"Minimum number of log counts required: " << numberOfLogs(N)<<endl;
}

出力

Minimum number of log counts required: 4