查找在C ++中计算对数N所需的最小对数值

我们知道log（x * y）= log(x)+ log(y)。因此，我们将看到计算从1到N的所有日志值所需的最小对数值数。因此，如果N为6，则输出将为3，从log(1)到log(6)，有除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