数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究在 C++ 中查找计算 Log upto N 所需的 Log 最小值
众所周知，log(x*y) = log(x) + log(y)。因此，我们将了解计算 1 到 N 的所有 log 值所需的最少 log 值是多少。因此，如果 N 为 6，则输出将为 3，因为从 log(1) 到 log(6)，除了 log(1) 之外还需要三个 log 值。由于 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 中找到素数，因为我们可以看到，对于素数，我们必须独立计算 log 值。否则，我们必须分解和计算。
示例
#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
更新日期： 18-Dec-2019
84 次浏览
广告