Future Number 1 (FUTURENUM)

Nguồn: LQDOJ Độ khó: Trung bình Sàng Eratosthenes Số nguyên tố Ước số

Đề bài

FUTURE NUMBER 1

Điểm: 300. Thời gian: 1.0s. Bộ nhớ: 64M. Input: bàn phím. Output: màn hình.

Định nghĩa: 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í dụ: $10$ có $2$ ước thực sự là $2$ và $5$ là các số nguyên tố nên $10$ là số "tương lai".

Yêu cầu: Cho dãy số nguyên $a_1, a_2, \ldots, a_n$ ($1 \le n \le 10^4$ với mọi $i$ sao cho $1 \le a_i \le 10^6$). Hãy cho biết trong dãy trên có bao nhiêu số tương lai.

Input:

• Dòng thứ nhất gồm số nguyên $n$.
• Dòng thứ hai gồm các số $a_1, a_2, \ldots, a_n$.

Output:

• Số lượng số tương lai thỏa đề.

Test 1 – input

9
9 7 10 6 17 4 19 21 13

Test 1 – output

5

Lời mở đầu

Bài này mình được một em học viên hỏi và mình đã hướng dẫn chi tiết cách thức giải quyết cho em ấy. Tin rằng sẽ có giá trị với nhiều bạn nên mình viết lại thành bài giải đầy đủ để các bạn tham khảo nhen. Hy vọng mang đến được giá trị cho các bạn 😇.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

Nộp bài trên CLUE OJ

Hiểu đề trước nè: không tính $1$ và chính nó, nếu từng ước số còn lại đều là số nguyên tố thì số đó là số "tương lai". Ví dụ số $10$ có 4 ước là $1, 2, 5, 10$; bỏ $1$ và $10$ thì chỉ còn $2$ và $5$, cả hai đều là số nguyên tố ⇒ $10$ thỏa mãn. Việc của mình là đếm xem trong dãy $n$ số có bao nhiêu số như vậy.

Với test của đề, mình xét lần lượt từng số:

Số	Ước thực sự (bỏ 1 và chính nó)	Tương lai?
9	3	✅
7	(không có)	❌
10	2, 5	✅
6	2, 3	✅
17	(không có)	❌
4	2	✅
19	(không có)	❌
21	3, 7	✅
13	(không có)	❌

Có 5 số tương lai là $9, 10, 6, 4, 21$ ⇒ đáp án 5. Để ý là các số nguyên tố ($7, 17, 19, 13$) không được tính vì chúng chẳng có ước thực sự nào cả. Số $1$ cũng vậy.

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Cách 1Hàm kiểm tra nguyên tố riêng · O(n · √X · √X)Cách 2Sàng Eratosthenes · O(X log log X + n√X)

Cách 1Liệt kê ước + hàm kiểm tra nguyên tố – O(n · √X · √X)

Muốn biết $x$ có phải số tương lai không thì mình cần phân tích xem $x$ (không tính $1$ và chính nó) có những ước số cụ thể là số nào. Đây chính là bài toán quen thuộc: liệt kê các ước số của một số.

Cách liệt kê ước nhanh là chỉ cho $i$ chạy từ $2$ đến $\sqrt{x}$: mỗi khi $x$ chia hết cho $i$ thì ta có luôn một cặp ước là $i$ và $\dfrac{x}{i}$. Cặp này đi chung với nhau nên chỉ cần duyệt tới $\sqrt{x}$ là gặp đủ hết các ước rồi.

Ý chính

Với $x \gt 1$ và $x$ không phải số nguyên tố: duyệt $i = 2, 3, \ldots$ khi $i \cdot i \le x$. Gặp $x \bmod i = 0$ thì kiểm tra cả hai ước $i$ và $x / i$. Chỉ cần một trong hai không phải số nguyên tố là kết luận $x$ không phải số tương lai và dừng sớm luôn.

Một nhận xét nhỏ: với số nguyên dương $x$ bất kỳ, ước số lớn nhất của nó chính là $x$, còn các ước khác đều nhỏ hơn $x$ (vì đã là ước thì $x$ phải chia hết cho nó). Bỏ chính nó ra thì ước lớn nhất chỉ còn tối đa là $\dfrac{x}{2}$. Với $a_i \le 10^6$ thì mọi ước cần kiểm tra đều nằm trong đoạn $[2, 5 \cdot 10^5]$.

Ở cách này, mỗi ước mình kiểm tra nguyên tố bằng một hàm riêng isPrime(v) thử chia từ $2$ đến $\sqrt{v}$.

Source code để các bạn tham khảo nếu làm theo hướng này:

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

bool isPrime(int x){
    if(x < 2) return false;
    for(int i = 2; i * i <= x; ++i){
        if(x % i == 0) return false;
    }
    return true;
}

int main(){
    int n;
    cin >> n;
    int res = 0;
    while(n--){
        int x;
        cin >> x;
        if(x > 1 && !isPrime(x)){
            bool flag = true;
            for(int i = 2; i * i <= x; ++i){
                if(x % i == 0){
                    if(!isPrime(i) || !isPrime(x / i)){
                        flag = false;
                        break;
                    }
                }
            }
            if(flag) res++;
        }
    }
    cout << res;
    return 0;
}

import sys


def is_prime(x):
    if x < 2:
        return False
    i = 2
    while i * i <= x:
        if x % i == 0:
            return False
        i += 1
    return True


def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    res = 0
    for k in range(1, n + 1):
        x = int(data[k])
        if x > 1 and not is_prime(x):
            flag = True
            i = 2
            while i * i <= x:
                if x % i == 0:
                    if not is_prime(i) or not is_prime(x // i):
                        flag = False
                        break
                i += 1
            if flag:
                res += 1
    print(res)


main()

Đánh giá độ phức tạp của cách làm này:

• Không gian: $O(1)$, đọc số nào xử lý số đó.
• Thời gian: mỗi số tốn $O(\sqrt{X})$ để duyệt $i$, cộng thêm mỗi lần gặp ước thì gọi hàm kiểm tra nguyên tố tốn thêm $O(\sqrt{X})$. Thô nhất là $O(n \cdot \sqrt{X} \cdot \sqrt{X})$, với $X = 10^6$ là giá trị lớn nhất.

Không gian$O(1)$

Thời gian$O(n \cdot \sqrt{X} \cdot \sqrt{X})$

Với bài này thì sao?

Thực tế số lần gặp ước ít hơn nhiều so với $\sqrt{x}$ và vòng lặp còn dừng sớm, nên với giới hạn của bài này bản C++ vẫn chạy nhanh (mình đo test xấu nhất khoảng 0.3 giây). Nhưng bản Python thì chậm hơn hẳn (khoảng 10 giây) ⇒ chắc chắn TLE. Và quan trọng hơn là thói quen: khi phải kiểm tra nguyên tố cho cả một danh sách số nằm trong phạm vi nhỏ thì mình nên dùng sàng – xem cách 2 nhé.

Cách 2Sàng Eratosthenes + liệt kê ước – O(X log log X + n√X)

Một kinh nghiệm mình muốn các bạn ghi nhớ: nếu trong ngữ cảnh chỉ cần kiểm tra một hoặc vài số có là số nguyên tố hay không thì ta có thể tự viết một hàm kiểm tra riêng cho từng số. Nhưng với những bài toán cần kiểm tra cả một danh sách nhiều số, và biết rằng các số đó nằm trong một phạm vi nhỏ (kiểu từ $1$ đến tối đa $10^7$), thì tốt nhất đừng gọi hàm kiểm tra cho từng số nữa, mà hãy dùng sàng nguyên tố Eratosthenes.

Sàng một lần từ $1$ đến $N = 10^6$, sau đó với một số bất kỳ ta biết được ngay lập tức trong $O(1)$ nó có là số nguyên tố hay không, chỉ việc tra mảng isPrime. Bạn nào chưa biết sàng thì xem bài viết này nhé, đọc từ đầu đến hết phần "Sàng nguyên tố Eratosthenes": Lý thuyết số – VNOI Wiki.

Kế hoạch

1. Sàng Eratosthenes: isPrime[i] cho mọi $i \le 10^6$.
2. Với mỗi số $x$: bỏ qua nếu $x = 1$ hoặc $x$ là số nguyên tố (không có ước thực sự).
3. Duyệt $i$ từ $2$ khi $i \cdot i \le x$: gặp $x \bmod i = 0$ thì tra isPrime[i] và isPrime[x / i], một trong hai sai thì flag = false và thoát vòng lặp.
4. Cuối cùng flag vẫn đúng thì tăng res.

Minh hoạ xét các cặp ước

Các bạn nhập dãy số rồi bấm Tiếp để xem với mỗi số, $i$ chạy từ $2$ đến $\sqrt{x}$ như thế nào, gặp cặp ước $(i, x/i)$ thì tra bảng sàng ra sao (xanh = cặp ước đều nguyên tố, đỏ = có ước không nguyên tố ⇒ dừng sớm):

Dãy số (tối đa 10 số, mỗi số ≤ 3000)

Ví dụ nhanh:

Source code để các bạn tham khảo nếu làm theo hướng này (đây là code mình đã nộp AC):

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6;
bool isPrime[N + 1];

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for(int i = 0; i <= N; ++i){
        isPrime[i] = true;
    }
    isPrime[0] = false;
    isPrime[1] = false;
    for(int i = 2; i * i <= N; ++i){
        if(isPrime[i] == true){
            for(int j = i * i; j <= N; j += i)
                isPrime[j] = false;
        }
    }
    int n;
    cin >> n;
    int res = 0;
    while(n--){
        int x;
        cin >> x;
        if(!isPrime[x] && x > 1){
            bool flag = true;
            for(int i = 2; i * i <= x; ++i){
                if(x % i == 0){
                    if(!isPrime[i] || !isPrime[x / i]){
                        flag = false;
                        break;
                    }
                }
            }
            if(flag){
                res++;
            }
        }
    }
    cout << res;
    return 0;
}

import sys


def main():
    N = 10 ** 6
    is_prime = bytearray([1]) * (N + 1)
    is_prime[0] = 0
    is_prime[1] = 0
    i = 2
    while i * i <= N:
        if is_prime[i]:
            # gạch bỏ các bội i*i, i*i + i, ... (gán cả đoạn một lần cho nhanh)
            is_prime[i * i::i] = bytes(len(range(i * i, N + 1, i)))
        i += 1
    # Python chậm hơn C++ nhiều nên chỉ thử chia cho các số nguyên tố <= 1000
    # (ước nhỏ nhất > 1 của x luôn là số nguyên tố, kết quả không đổi)
    small = [p for p in range(2, 1001) if is_prime[p]]

    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    res = 0
    for k in range(1, n + 1):
        x = int(data[k])
        if not is_prime[x] and x > 1:
            flag = True
            for i in small:
                if i * i > x:
                    break
                if x % i == 0:
                    if not is_prime[x // i]:
                        flag = False
                        break
            if flag:
                res += 1
    print(res)


main()

Bản Python

Python chậm hơn C++ rất nhiều, nếu cho $i$ chạy qua mọi số từ $2$ đến $\sqrt{x}$ thì test xấu nhất mất khoảng 4.5 giây. Nên ở bản Python mình chỉ cho $i$ chạy qua các số nguyên tố $\le 1000$. Kết quả không đổi, vì nếu $x$ chia hết cho một hợp số $i$ thì nó cũng chia hết cho một ước nguyên tố $p \lt i$ của $i$, và khi đó $x / p$ chắc chắn là hợp số ⇒ đã bị loại ngay từ lúc gặp $p$ rồi.

Các bạn bấm chạy tay code C++ để xem từng dòng. Phần sàng chạy tới $10^6$ nên mình chỉ cho xem chi tiết vài giá trị $i$ đầu, phần còn lại gom thành một bước:

C++▶ Chạy tay từng dòng codeCách 2: sàng Eratosthenes rồi tra cặp ước (i, x/i) của từng số.

Dữ liệu vào (stdin) – sửa thoải mái9 9 7 10 6 17 4 19 21 13

Dữ liệu mẫu:

1#include <bits/stdc++.h>

2using namespace std;

3const int N = 1e6;

4bool isPrime[N + 1];

5

6int main(){

7 ios::sync_with_stdio(0);

8 cin.tie(0);

9 cout.tie(0);

10 for(int i = 0; i <= N; ++i){

11 isPrime[i] = true;

12 }

13 isPrime[0] = false;

14 isPrime[1] = false;

15 for(int i = 2; i * i <= N; ++i){

16 if(isPrime[i] == true){

17 for(int j = i * i; j <= N; j += i)

18 isPrime[j] = false;

19 }

20 }

21 int n;

22 cin >> n;

23 int res = 0;

24 while(n--){

25 int x;

26 cin >> x;

27 if(!isPrime[x] && x > 1){

28 bool flag = true;

29 for(int i = 2; i * i <= x; ++i){

30 if(x % i == 0){

31 if(!isPrime[i] || !isPrime[x / i]){

32 flag = false;

33 break;

34 }

35 }

36 }

37 if(flag){

38 res++;

39 }

40 }

41 }

42 cout << res;

43 return 0;

44}

ChậmVừaNhanhRất nhanh

Đánh giá độ phức tạp của cách làm này:

• Không gian: mảng isPrime có $10^6 + 1$ phần tử kiểu bool, khoảng 1 MB.
• Thời gian: bước sàng Eratosthenes từ $1$ đến $X$ có độ phức tạp $O(X \log \log X)$; với $X = 10^6$ thì cỡ hơn 4 triệu bước. Bước xét từng số: mỗi số tốn tối đa $\sqrt{X} = 10^3$ bước (nếu gặp ước không nguyên tố thì còn kết thúc sớm), mỗi lần tra sàng chỉ tốn $O(1)$. Có tối đa $n = 10^4$ số ⇒ $10^4 \cdot 10^3 = 10^7$ bước.
• Tổng cộng khoảng $4$ triệu $+ 10$ triệu $= 14$ triệu, nhỏ hơn nhiều so với ngưỡng 1 giây (khoảng 30 – 50 triệu, tối đa lắm là 100 triệu phép tính) nên các bạn yên tâm nha.

Không gian$O(X)$

Thời gian$O(X \log \log X + n\sqrt{X})$

Nhận xét thêm cho bạn nào thích toán

Thử nghĩ xem những số nào là số tương lai: nếu $x = p \cdot q$ với $p, q$ nguyên tố (có thể $p = q$, ví dụ $4 = 2 \cdot 2$, $9 = 3 \cdot 3$) thì ước thực sự chỉ có $p$ và $q$ ⇒ thỏa. Còn nếu $x$ có từ 3 thừa số nguyên tố trở lên (ví dụ $8 = 2 \cdot 2 \cdot 2$, $12 = 2 \cdot 2 \cdot 3$) thì sẽ có một ước thực sự là tích của 2 thừa số ⇒ hợp số ⇒ không thỏa. Vậy số tương lai chính là các số bằng tích đúng hai số nguyên tố. Code ở trên đúng với nhận xét này, các bạn có thể tự kiểm chứng nhé.

Ghi chú của mình: code C++ và Python của cả 2 cách cho đúng output test của đề, và đã được kiểm tra với 300 bộ test ngẫu nhiên ($n \le 30$, $a_i \le 2000$), so với code vét cạn liệt kê mọi ước – khớp hết. Với $n = 10^4$ số đều bằng $994\,009 = 997^2$ (phải duyệt hết tới $\sqrt{x}$): cách 1 C++ khoảng 0.3 giây, Python khoảng 10 giây; cách 2 C++ khoảng 0.15 giây, Python khoảng 0.5 giây.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇