查找在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