หาจำนวนค่า Log ขั้นต่ำที่ต้องการเพื่อคำนวณ Log จนถึง N ใน C++

เรารู้ว่า log(x*y) = log(x) + log(y) เราจะดูว่าต้องการค่า log ขั้นต่ำกี่ค่า เพื่อคำนวณค่า log ทั้งหมดจาก 1 ถึง N ดังนั้นถ้า N คือ 6 ผลลัพธ์จะเป็น 3 เพราะจาก log(1) ถึง log(6) ต้องการค่า log 3 ค่า ไม่รวม 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 เนื่องจากเราเห็นว่าสำหรับจำนวนเฉพาะ เราต้องคำนวณค่า 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