Bài toán
Đếm số lượng số nguyên tố nhỏ hơn n.
Độ phức tạp
Thuật toán này dùng chạy tốt với n=10^10.
Code này của Nguyễn Tiến Trung Kiên
#include <math.h>
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
using namespace std;
#define long long long
const int N = 100005;
const int M = 1000000007;
bool np[N];
int p[N], pp = 0;
void eratos() {
np[0] = np[1] = true;
for (int i = 2; i * i < N; i++)
if (!np[i])
for (int j = i * i; j < N; j += i) np[j] = true;
for (int i = 2; i < N; i++)
if (!np[i]) p[++pp] = i;
}
long power(long a, long k) {
long P = 1;
while (k) {
if (k & 1) P = P * a;
k /= 2;
a = a * a;
}
return P;
}
long power(long a, long k, long M) {
long P = 1;
for (a = a % M; k; k /= 2) {
if (k & 1) P = P * a % M;
a = a * a % M;
}
return P;
}
long root(long n, long k) {
long x = pow(n, 1.0 / k);
while (power(x, k) % M == power(x, k, M) && power(x, k) < n) x++;
while (power(x, k) % M != power(x, k, M) || power(x, k) > n) x--;
return x;
}
map<long, long> Phi[N];
long phi(long x, int a) {
if (Phi[a].count(x)) return Phi[a][x];
if (a == 1) return (x + 1) / 2;
long Result = phi(x, a - 1) - phi(x / p[a], a - 1);
return Phi[a][x] = Result;
}
long pi(long x) {
if (x < N)
return upper_bound(p + 1, p + pp + 1, x) - (p + 1);
long a = pi(root(x, 4));
long b = pi(root(x, 2));
long c = pi(root(x, 3));
long Sum = phi(x, a) + (b + a - 2) * (b - a + 1) / 2;
for (int i = a + 1; i <= b; i++)
Sum -= pi(x / p[i]);
for (int i = a + 1; i <= c; i++) {
long bi = pi(root(x / p[i], 2));
for (int j = i; j <= bi; j++)
Sum -= pi(x / p[i] / p[j]) - (j - 1);
}
return Sum;
}
int main() {
eratos();
long n;
while (cin >> n)
cout << pi(n) << endl;
}
Nhận xét
Code này đã được kiểm tra.
Tham khảo
http://mathworld.wolfram.com/LehmersFormula.html
http://en.wikipedia.org/wiki/Prime-counting_function#Table_of_.CF.80.28x.29.2C_x_.2F_ln_x.2C_and_li.28x.29