जैसा कि हम जानते हैं कि log(x*y) =log(x) + log(y). तो हम देखेंगे कि 1 से N तक के सभी लॉग मानों की गणना करने के लिए न्यूनतम लॉग मानों की क्या आवश्यकता है। इसलिए यदि N 6 है, तो आउटपुट 3 होगा, जैसे लॉग (1) से लॉग (6) तक, वहाँ हैं लॉग (1) को छोड़कर तीन लॉग मानों की आवश्यकता है। चूंकि लॉग (1) हमेशा 0 होता है, फिर इसे अनदेखा करें, अब लॉग (2) और लॉग (3) के लिए, हमें खोजना होगा। उसके बाद लॉग (4) के लिए यह लॉग (2) + लॉग (2) है, लेकिन लॉग (2) का मान ज्ञात है, इसलिए हम इसे फिर से गणना नहीं करते हैं, लॉग (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