N পর্যন্ত লগ মান বের করতে ন্যূনতম লগ ভ্যালুর সংখ্যা বের করা C++-তে

যেহেতু আমরা জানি log(x*y) = log(x) + log(y)। তাই আমরা দেখব ১ থেকে N পর্যন্ত সব লগ মান বের করতে ন্যূনতম কতগুলো লগ ভ্যালু লাগবে। তাই যদি N হয় 6, তবে আউটপুট হবে 3, কারণ log(1) থেকে log(6) পর্যন্ত তিনটি লগ ভ্যালু লাগবে log(1) বাদে। কারণ log(1) সবসময় ০, তাই এটিকে বাদ দিন, এখন log(2) এবং log(3) এর জন্য আমাদের বের করতে হবে। তারপর log(4) এর জন্য এটি log(2) + log(2), কিন্তু log(2) এর মান জানা, তাই আবার হিসাব করতে হবে না, log(5) এর জন্য আমাদের বের করতে হবে। তাই এখন কাউন্ট হল ৩, log(6) = log(3) + log(2), তারা ইতিমধ্যে জানা, তাই কাউন্ট ৩।

এই সমস্যাটি ১ থেকে 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