Như chúng ta biết rằng log (x * y) =log (x) + log (y). Vì vậy, chúng ta sẽ thấy số lượng giá trị log nhỏ nhất được yêu cầu để tính tất cả các giá trị log từ 1 đến N. Vì vậy, nếu N là 6, thì đầu ra sẽ là 3, như từ log (1) đến log (6), có ba giá trị nhật ký được yêu cầu ngoại trừ nhật ký (1). Vì log (1) luôn là 0, nên bỏ qua nó, bây giờ đối với log (2) và log (3), chúng ta phải tìm. Sau đó đối với log (4) đây là log (2) + log (2), nhưng giá trị của log (2) đã biết, vì vậy chúng ta không tính toán lại điều này, đối với log (5), chúng ta cần tính toán. Vì vậy, bây giờ số đếm là 3, log (6) =log (3) + log (2), chúng đã được biết, vì vậy số đếm là 3.
Bài toán này có thể được rút gọn để tìm các số nguyên tố trong phạm vi từ 1 đến N, vì chúng ta có thể thấy rằng đối với các số nguyên tố, chúng ta phải tính các giá trị log một cách độc lập. Nếu không, chúng ta phải phân tích và tính toán.
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;
} Đầu ra
Minimum number of log counts required: 4