हम जानते हैं कि 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) के लिए, हमें गणना करने की आवश्यकता है। तो अब काउंट 3 है, log(6) = log(3) + log(2), वे पहले से ज्ञात हैं, तो काउंट 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
