C++에서 Log upto N을 계산하는 데 필요한 최소 Log 값 찾기

우리가 알고 있듯이 log(x*y) =log(x) + log(y). 따라서 우리는 1에서 N까지의 모든 로그 값을 계산하는 데 필요한 최소 로그 값 수를 알 수 있습니다. 따라서 N이 6이면 출력은 log(1)에서 log(6)과 같이 3이 됩니다. log(1)을 제외한 세 개의 로그 값이 필요합니다. log(1)은 항상 0이므로 무시하십시오. 이제 log(2) 및 log(3)에 대해 찾아야 합니다. 그 후 log(4)의 경우 이것은 log(2)+ log(2)이지만 log(2)의 값을 알고 있으므로 이를 다시 계산하지 않습니다. log(5)의 경우 계산해야 합니다. 이제 count는 3, log(6) =log(3) + log(2)이며 이미 알려져 있으므로 count는 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