---
tags: VNOJ, THT, Sieve, Binary Search, Online Query, SPyofgame
---

Tin học trẻ 2021 - Vòng sơ khảo - Bảng C - Xếp gạch
===

[https://oj.vnoi.info/problem/tht21_skc_brick](https://oj.vnoi.info/problem/tht21_skc_brick)

-----

###### Tags: `Sieve`, `Binary Search`, `Online Query`

-----
### Hướng dẫn

Mình cần tìm $min(n - k)$ với $k$ là tích của 2 số nguyên tố liên tiếp không quá $n$ $\Rightarrow$ cần tìm só $k$ lớn nhất.

Vì $k$ là tích của $2$ số nguyên tố liền kề không quá $max(n) = 10^{12}$ nên $k < 1000036000099 = 1000003 \times 1000033$, nghĩa là ta cần biết các số nguyên tố tính đến $1000033$ (cụ thể là số nguyên tố thứ $78499$)

Vậy thì ta cần [sàng nguyên tố](https://hackmd.io/4N-JNh6GToSt_wVRhREKqg?view) để lấy các số nguyên tố cần thiết cho bài toán này. Sau đó dựng mảng gồm $X[]$ có $X[i]$ là tích của 2 số nguyên tố thứ $i$ và $i + 1$.

Lúc này nhận xét dãy đơn điệu tăng nên ta có thể sử dụng chặt nhị phân để tìm kiếm số $K$ lớn nhất thỏa mãn cho mỗi $N$

-----
### Code

> Với $V = \sqrt{max(n)}$
> Với $\pi(n) \approx \frac{n}{\ln n}$ là số lượng số nguyên tố tính đến $n$
> **Time:** $O(V + q \times \log_2\pi(V))$
> **Space:** $O(V) + O(\pi(V))$
> **Algo:** Sieve, Binary Search, Online Query

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;
#define all(x) (x).begin(), (x).end()

/// [SPyofame Linear Sieve](https://hackmd.io/@Editorial-Slayers/sieve)
vector<int> prime;
vector<int> lpf;
void sieve(int n)
{
    prime.assign(1, 2);
    lpf.assign(n + 1, 2);

    for (int x = 3; x <= n; x += 2)
    {
        if (lpf[x] == 2) prime.push_back(lpf[x] = x);
        for (int i = 0; i < prime.size() && prime[i] <= lpf[x] && prime[i] * x <= n; ++i)
            lpf[prime[i] * x] = prime[i];
    }
}

int main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(NULL);

    sieve(1e6 + 61);
    vector<ll> multi(prime.size() - 1);
    for (int i = 0; i < multi.size(); ++i)
        multi[i] = 1LL * prime[i] * prime[i + 1];
    
    int q;
    cin >> q;
    while (q-->0)
    {
        ll n;
        cin >> n;
        cout << n-*--upper_bound(all(multi), n) << "\n";
    }

    return 0;
}

-----
### Bonus

- Bạn có thể làm bài này trong $O(q \log_2 q + V)$ thời gian không ?