$\Huge \text{Số "tương lai" 4 (Bản thử)}$

###### Gắn thẻ: `Sàng nguyên tố`, `Mảng cộng dồn`, `Tối ưu hóa`
###### Tác giả: [dang7rickroll](https://lqdoj.edu.vn/user/dang7rickroll)

---
Vì thấy ít người AC quá nên mình xin đóng góp lời giải bài này như sau:
# Các bước thực hiện
Các bước tuần tự để thực hiện bài toán này là như sau:
1. Sàng nguyên tố & đánh dấu (sàng mình sử dụng ở đây là sàng Eratosthenes) - [Tìm hiểu về sàng Eratosthenes](https://vi.wikipedia.org/wiki/S%C3%A0ng_Eratosthenes)
2. Sử dụng mảng tổng dồn để tính tổng các số tương lai đánh dấu được và giải thích.
3. Thực hiện bài toán đề ra

# Nhắc lại về lý thuyết & nhận xét
Trước khi bắt đầu phần hướng dẫn, chúng ta hãy cùng nhớ lại định nghĩa của số "tương lai:"
> [color=red] Số "tương lai" là số có các ước (không kể 1 và chính nó) là các số nguyên tố.

Vậy ta có thể "biến đổi" định nghĩa trên thành một định nghĩa khác "dễ hiểu" hơn:
> [color=blue] Số tương lai là số có dạng: $p\times q$ trong đó $p,q$ là các số nguyên tố.

Vậy số "tương lai" là số sao cho tồn tại hai số $p$ và $q$ đều là số nguyên tố ($p$ và $q$ có thể giống nhau).

# Thuật toán
Dựa vào nhận xét trên, ta rút ra được tư tưởng của thuật toán:
- Trước hết, ta phải lọc ra tất cả các số nguyên tố từ $2$ đến $3 \times 10^7$ (do $0$, $1$ không phải là số nguyên tố nên sẽ rút lại để tiết kiệm một chút thời gian). Các số nguyên tố lọc ra được cho vào một **mảng** (hoặc **vector** trong `C++`) để thuận tiện cho việc thao tác sau này.
> Để tiện cho việc gọi tên, mình sẽ gọi mảng/vector chứa các số nguyên tố lọc được là mảng $prime$ nhé.
> Đặt $3 \times 10^7 = LIM$

- Ta sẽ chạy trên mảng $prime$ từ $0$ hoặc $1$ đến $\sqrt{LIM}$ (gọi vòng chạy là là vòng `for` $i$), tiếp đó ta sẽ đặt một vòng `for` $j$ ở trong vòng `for` $i$ ($j$ ở đây là bằng $\frac{n}{i}$ và $j$ phải lớn hơn $i$).
- Trong vòng for $j$ này, ta sẽ lưu vào một mảng khác tất cả các tích $prime_i \times prime_j$ (gọi mảng này là mảng $res$) để lát nữa thực hiện việc **cộng dồn**.
- Sắp xếp tăng dần lại mảng $res$ để thực hiện cộng dồn chính xác.
- Ta sẽ cộng dồn trên mảng $res$, đưa tất cả các kết quả thực hiện được vào mảng cộng dồn (gọi mảng này là mảng $sum$.
- Ở chương trình chính, ta sẽ thực hiện $Q$ truy vấn trên mảng sum bằng công thức `sum[r] - sum[l - 1]`.
- Tuy nhiên, có thể $l$ và $r$ không phải là số tương lai nên chúng ta cần phải tìm ra số bé nhất, lớn hơn $l$ là số đó là số tương lai và số lớn nhất, bé hơn $r$ và số đó là số tương lai. Sau đó mới có thể dùng công thức tính tổng trên.

# Code tham khảo cho thuật:
> Code của[color=red] [dang7rickroll](https://lqdoj.edu.vn/user/dang7rickroll)
> Độ phức tạp: $O(3 \times 10^7)$
> Thuật sử dụng: `Sàng nguyên tố`,`Mảng tổng dồn`
:::info
:::spoiler Code

//futurenum4
#include<bits/stdc++.h>
using namespace std;

#define int long long

vector<int>prime = {2};
vector<int>sum; // mang tong don
vector<int>res; // mang chua so tuong lai

int n;

const int N = 3e7; //gioi han

void sieve() { //sang + danh dau
	vector <bool> isPrime(N / 2 + 1, true);
    isPrime[0] = false;
    isPrime[1] = false;
    for(int i = 3; i <= N / 2; i += 2) {
         if(isPrime[i] == true) {
         	 prime.push_back(i);
             for(int j = i * i; j <= N / 2; j += i * 2)
                 isPrime[j] = false;
        }
    }
}

void process()
{
	int y = 0;
	for (int i = 0; prime[i] * prime[i] <= N; i++)
	{
		for (int j = i; j < prime.size() && prime[i] * prime[j] <= N; j++)
		{
			res.push_back(prime[i] * prime[j]);
		}
	}
	sort(res.begin(), res.end()); // sort de thuc hien mang tong don (PREFIX SUM)
	sum.push_back(0);
	for (int i = 0; i < res.size(); i++)
	{
		y += res[i];
		sum.push_back(y); // cong don so tuong lai
	}
}

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  sieve();
  process();
  cin >> n;
  while (n--)
  {
  	int l,r;
  	cin >> l >> r;
  	l = lower_bound(res.begin(), res.end(), l) - res.begin() + 1;
  	r = upper_bound(res.begin(), res.end(), r) - res.begin();
  	cout << sum[r] - sum[l - 1] << '\n';
  }
  return 0;
}

:::
### Giải thích code
- `const int N = 3e7` - chính là $LIM$ của bài toán.
- Hàm `sieve()`: Hàm này dùng để sàng ra các số nguyên tố không quá $3\times 10^7$, đồng thời đưa các số nguyên tố lọc được vào một vector `prime` bằng lệnh `prime.push_back(i)`. Sàng Eratosthenes đã được tối ưu này có ưu điểm là chạy nhanh hơn sàng Eratosthenes bình thường, rất tiết kiệm thời gian.
- Code này chỉ đúng được 90% test, nên để cần AC test cuối ta cần tối ưu hơn nữa

# Tối ưu hóa (Deep - Optimized)
- Ta nhận thấy rằng: Từ $1$ đến $LIM$, giá trị $prime_i \times prime_j$ sẽ nằm ở vị trí $prime_i \times prime_j$ (nó giống như việc số $3$ nằm ở vị trí thứ $3$ từ $1$ đến $10$ ấy). Công việc này sẽ giảm đáng kể thời gian dùng để `sort` lại mảng `res`. Vì thế bạn sẽ thay câu lệnh:

res.push_back(prime[i] * prime[j]);

bằng câu lệnh:

sum[prime[i] * prime[j]] = prime[i] * prime[j];

- Ta sẽ lưu trực tiếp giá trị $prime_i \times prime_j$ vào vị trí thứ $prime_i \times prime_j$ ở trong mảng `sum` (mảng cộng dồn). Và khi kết thúc gán, ta chỉ việc cộng dồn lại mảng (bỏ đi phần code từ dòng 40 đến dòng 44) và thay bằng vòng lặp mảng cộng dồn (cái này chắc các bạn cũng biết :D)

:::info
:::spoiler Code

//futurenum4
#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N = 3e7; //gioi han

vector<int>prime = {2}; // so nguyen to
vector<int>sum (N + 1); // mang tong don
//vector<int>res; // mang chua so tuong lai - khong can thiet vi da optimize (toi uu) code

int n;

int L, R;

void sieve() { //sang + danh dau
	vector <bool> isPrime(N / 2 + 1, true);
    isPrime[0] = false;
    isPrime[1] = false;
    for(int i = 3; i <= N / 2; i += 2) {
         if(isPrime[i] == true) {
         	 prime.push_back(i);
             for(int j = i * i; j <= N / 2; j += i * 2)
                 isPrime[j] = false;
        }
    }
}

void process() // su dung ham process so tuong lai 3
{
	sum.assign(N,0);
	int y = 0;
	for (int i = 0; prime[i] * prime[i] <= N; i++)
	{
		for (int j = i; j < prime.size() && prime[i] * prime[j] <= N; j++)
		{
		//	dat prime[i]*prime[j] o vi tri prime[i]*prime[j], toi uu thoi gian & bo nho
			sum[prime[i] * prime[j]] = prime[i] * prime[j];
		}
	}
	//khong can sort
	sum.push_back(0);
	for (int i = 1; i < N; i++)
	{
		sum[i] += sum[i - 1];
	}
}

signed main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  sieve(); //sang
  process(); //xu ly
  cin >> n; //so truy van
  while (n--)
  {
  	int l,r;
  	cin >> l >> r;
  	cout << sum[r] - sum[l - 1] << '\n'; //tra loi cho tung truy van
  }
  return 0;
}

:::

---
Vậy là mình đã hướng dẫn xong bài **Số "tương lai" 4**. Vì kỹ năng viết còn yếu nên nếu các bạn thắc mắc bất cứ gì, cứ bình luận ở phần comment, mình sẽ chỉnh sửa và giải thích cho các bạn. Cảm ơn các bạn rất nhiều !