資料結構
網路
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 次瀏覽
廣告