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