আমরা জানি যে 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
