/** * Sergey Kopeliovich (burunduk30@gmail.com) */ #include using namespace std; #define forn(i, n) for (int i = 0; i < (int)(n); i++) #define all(a) (a).begin(), (a).end() const int N = 1e7; // N ---> N^{1/2} const int PN = 1e6; // N/lnN // bool is[N]; int d[N]; int pn, p[PN]; int main() { // O(NloglogN) // for (int i = 2; i * i < N; i++) // if (!is[i]) // for (int j = i * i; j < N; j += i) // is[j] = 1; // for (int i = 2; i < N; i++) // if (!is[i]) // p[pn++] = i; // O(N) for (int y = 2; y < N; y++) { if (d[y] == 0) { d[y] = y; p[pn++] = y; } for (int ip = 0; ip < pn && p[ip] <= d[y] && y * p[ip] < N; ip++) { d[y * p[ip]] = p[ip]; } } // divs[1] = 1; // for (int i = 2; i < N; i++) { // int j = i / d[i]; // deg[i] = 1 + (d[j] == d[i] ? deg[j] : 0); // y[i] = (d[j] == d[i] ? y[j] : j); // divs[x] = divs[y[i]] * (deg[i] + 1); // } double c1 = 10, c2 = 0; for (int i = pn / 2; i < pn; i++) { int k = i + 1; int x = p[i]; double coef = x / (k * log(k)); c1 = min(c1, coef); c2 = max(c2, coef); } printf("[%.6f ... %.6f]\n", c1, c2); cout << N / log(N) << endl; cout << pn << endl; }