Vì log(x*y)=log(x)+log(y). Tìm số lượng giá trị log cần tính từ 1 đến N. Ví dụ N=6 → 3 (log2, log3, log5).
Bài toán quy về tìm số nguyên tố ≤ N, vì log số hợp thành có thể phân tích từ log số nguyên tố.
Ví dụ
#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; }
Kết quả
Minimum number of log counts required: 4