Chương 20 - Prime Number

Chương cuối của Level 1, mang tinh thần “number theory cơ bản”. Prime number không phải pattern lớn trong phỏng vấn Big Tech (Google đôi khi hỏi), nhưng học để có Sàng Eratosthenes trong tủ vũ khí - thuật toán cổ điển vẫn rất hữu dụng.

Mục tiêu chương

Sau chương này, bạn sẽ:

• Thuộc sàng Eratosthenes O(n log log n).
• Trial division O(sqrt(n)) cho factorization 1 số.
• Pattern union với prime factors cho graph implicit (LC 952).
• Hằng số phổ biến: MOD = 10^9 + 7 (prime).

Khi nào dùng pattern này?

• Đề hỏi: liệt kê / đếm số nguyên tố, kiểm tra nguyên tố, phân tích thừa số.
• Ứng dụng: rolling hash (Chương 34), hashing modulo prime, …
• Hằng số phổ biến: 10^9 + 7 (prime để mod), 998244353 (FFT-friendly).

Template code

def is_prime(n: int) -> bool:
    """Trial division O(sqrt(n))."""
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0:
        return False
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False
        i += 2
    return True


def sieve(n: int) -> list[bool]:
    """Sàng Eratosthenes - O(n log log n)."""
    is_p = [True] * (n + 1)
    is_p[0] = is_p[1] = False
    for i in range(2, int(n ** 0.5) + 1):
        if is_p[i]:
            for j in range(i * i, n + 1, i):
                is_p[j] = False
    return is_p


def prime_factors(n: int) -> list[int]:
    """Phân tích thừa số - O(sqrt(n))."""
    factors: list[int] = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors

Bài tự luyện cuối chương

• LC 263 - Ugly Number
• LC 1175 - Prime Arrangements
• LC 1390 - Four Divisors
• LC 1819 - Number of Different Subsequences GCDs
• LC 2761 - Prime Pairs With Target Sum

---

20.1 Count Primes (LC 204)

Đề bài

Cho n. Trả về số nguyên tố nhỏ hơn n.

Ví dụ

Input:  n = 10   → 4
Giải thích: primes < 10 = {2, 3, 5, 7}.

Input:  n = 0    → 0
Input:  n = 1    → 0

Ràng buộc

• 0 <= n <= 5·10^6

Clarifying questions

• n = 0 hoặc 1? → Trả 0.
• n cực lớn? → Tối đa 5·10^6 theo LC.

Hướng tiếp cận

Brute force - trial division mỗi số, O(n sqrt n). TLE với n = 5·10^6.

Sàng Eratosthenes - O(n log log n).

is_prime[] mảng boolean. Với mỗi i từ 2, nếu is_prime[i] thật → mark tất cả bội số (i*i, i*i+i, i*i+2i, ...) là composite.

Hình minh hoạ với n = 30:

i=2: mark 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28
i=3: mark 9, 12, 15, 18, 21, 24, 27
i=4: composite → skip
i=5: mark 25
i=6..29: hoặc composite hoặc i² > 30 → skip

Còn lại: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 → 10 primes.

Code Python 3

class Solution:
    def countPrimes(self, n: int) -> int:
        if n < 2:
            return 0
        is_p = [True] * n
        is_p[0] = is_p[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if is_p[i]:
                # Bắt đầu từ i*i - các bội nhỏ hơn đã bị mark bởi prime nhỏ hơn.
                for j in range(i * i, n, i):
                    is_p[j] = False
        return sum(is_p)

Phân tích độ phức tạp

• Thời gian: O(n log log n).
• Bộ nhớ: O(n).

Bình luận

• Tối ưu space - bit set: dùng bytearray thay list[bool] để giảm 8x bộ nhớ.
• Bẫy: loop ngoài chỉ chạy đến sqrt(n) (vì mọi composite < n đều có thừa số ≤ sqrt(n)).
• Tại sao bắt đầu từ i*i? Các bội nhỏ hơn (2i, 3i, ..., (i-1)i) đã bị mark bởi các prime nhỏ hơn i.

Bài tự luyện liên quan

• LC 952 - Largest Component Size by Common Factor.
• LC 2521 - Distinct Prime Factors.

---

20.2 Ugly Number II (LC 264)

Đề bài

Ugly Number = số nguyên dương có dạng 2^a · 3^b · 5^c. Trả về ugly number thứ n. (1 cũng là ugly.)

Ví dụ

Input:  n = 10
Output: 12
Giải thích: 10 ugly đầu = 1, 2, 3, 4, 5, 6, 8, 9, 10, 12.

Ràng buộc

• 1 <= n <= 1690

Clarifying questions

• n có thể = 0? → Theo đề: n ≥ 1.
• Ugly bao gồm 1? → Có.

Hướng tiếp cận

Brute force đếm và check từng số - quá chậm khi n lớn.

3 con trỏ DP - O(n).

ugly[k] = ugly thứ k. Mỗi ugly mới = min(ugly[i2]*2, ugly[i3]*3, ugly[i5]*5). Sau khi chọn, advance pointer tương ứng.

Hình minh hoạ:

ugly = [1]                       i2=i3=i5=0
n2=1*2=2, n3=1*3=3, n5=1*5=5     min=2 → ugly=[1,2], i2=1
n2=2*2=4, n3=3, n5=5             min=3 → ugly=[1,2,3], i3=1
n2=4, n3=2*3=6, n5=5             min=4 → ugly=[1,2,3,4], i2=2
n2=3*2=6, n3=6, n5=5             min=5 → i5=1
n2=6, n3=6, n5=2*5=10            min=6 → i2=3, i3=2
...

Code Python 3

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        ugly = [1]
        i2 = i3 = i5 = 0
        while len(ugly) < n:
            next_ugly = min(ugly[i2] * 2, ugly[i3] * 3, ugly[i5] * 5)
            ugly.append(next_ugly)
            if next_ugly == ugly[i2] * 2:
                i2 += 1
            if next_ugly == ugly[i3] * 3:
                i3 += 1
            if next_ugly == ugly[i5] * 5:
                i5 += 1
        return ugly[-1]

Phân tích độ phức tạp

• Thời gian: O(n). Bộ nhớ: O(n).

Bình luận

• Bẫy if elif: dùng if (không elif) - vì ugly có thể bằng cả 2 cách (vd 6 = 2*3 = 3*2), nếu dùng elif thì 1 pointer không advance → duplicate.
• Heap version cũng được nhưng O(n log n) - chậm hơn DP.

Bài tự luyện liên quan

• LC 263 - Ugly Number.
• LC 313 - Super Ugly Number (tổng quát hoá).
• LC 1201 - Ugly Number III.

---

20.3 Prime Arrangements (LC 1175)

Đề bài

Cho n. Đếm số hoán vị của 1..n sao cho mọi số nguyên tố đứng tại vị trí prime (index 1-based). Modulo 10^9 + 7.

Ví dụ

Input:  n = 5
Output: 12
Giải thích: 5 vị trí, có 3 prime (2, 3, 5). Số prime trong 1..5 = 3.
            3! * 2! = 6 * 2 = 12.

Ràng buộc

• 1 <= n <= 100

Clarifying questions

• n = 1? → 1 hoán vị, prime 0 → 1·1=1.

Hướng tiếp cận

Counting: Gọi p = số prime ≤ n. Có p! cách xếp prime vào p vị trí prime, và (n - p)! cách xếp non-prime vào n - p vị trí non-prime.

Đáp án = p! * (n - p)! mod (10^9 + 7).

Code Python 3

from math import factorial

class Solution:
    MOD = 10**9 + 7

    def numPrimeArrangements(self, n: int) -> int:
        # Đếm prime ≤ n.
        if n < 2:
            return 1
        is_p = [True] * (n + 1)
        is_p[0] = is_p[1] = False
        for i in range(2, int(n ** 0.5) + 1):
            if is_p[i]:
                for j in range(i * i, n + 1, i):
                    is_p[j] = False
        p = sum(is_p)
        return (factorial(p) * factorial(n - p)) % self.MOD

Phân tích độ phức tạp

• Thời gian: O(n log log n) cho sàng.
• Bộ nhớ: O(n).

Bình luận

• Bài Easy - chỉ test bạn nhớ sàng và hiểu counting.

Bài tự luyện liên quan

• LC 204 - Count Primes.

---

20.4 Closest Prime Numbers in Range (LC 2523)

Đề bài

Cho left, right. Trả về cặp prime (p, q) với left <= p < q <= right mà q - p min. Nếu hoà, lấy cặp có p nhỏ hơn. Không có → [-1, -1].

Ví dụ

Input:  left=10, right=19
Output: [11, 13]

Ràng buộc

• 1 <= left <= right <= 10^6

Clarifying questions

• Range không chứa prime? → Trả [-1, -1].

Hướng tiếp cận

1. Sàng tới right, lấy danh sách prime trong [left, right].
2. Duyệt cặp kề nhau trong list, lấy min gap.

Code Python 3

from typing import List

class Solution:
    def closestPrimes(self, left: int, right: int) -> List[int]:
        is_p = [True] * (right + 1)
        is_p[0] = is_p[1] = False
        for i in range(2, int(right ** 0.5) + 1):
            if is_p[i]:
                for j in range(i * i, right + 1, i):
                    is_p[j] = False
        primes = [i for i in range(left, right + 1) if is_p[i]]
        if len(primes) < 2:
            return [-1, -1]
        best_gap = float('inf')
        result = [-1, -1]
        for i in range(len(primes) - 1):
            gap = primes[i + 1] - primes[i]
            if gap < best_gap:
                best_gap = gap
                result = [primes[i], primes[i + 1]]
        return result

Phân tích độ phức tạp

• Thời gian: O(right log log right).
• Bộ nhớ: O(right).

Bình luận

• Edge: primes consecutive (twin primes) → gap = 2; bài này muốn tìm cặp này nếu có.

Bài tự luyện liên quan

• LC 204 - Count Primes.

---

20.5 Largest Component Size by Common Factor (LC 952)

Đề bài

Cho nums. Nối 2 phần tử cùng component nếu chúng chia sẻ ít nhất 1 thừa số nguyên tố > 1. Trả về kích thước component lớn nhất.

Ví dụ

Input:  nums = [4, 6, 15, 35]   → 4
Giải thích: 4,6 chia sẻ 2; 6,15 chia sẻ 3; 15,35 chia sẻ 5 → tất cả 1 component.

Ràng buộc

• 1 <= len(nums) <= 2·10^4
• 1 <= nums[i] <= 10^5

Clarifying questions

• nums có thể chứa 1? → 1 không có thừa số prime → 1 đứng 1 component riêng.

Hướng tiếp cận

Insight: thay vì union các phần tử trực tiếp (cần O(n²)), ta union phần tử với mỗi thừa số prime của nó. Hai phần tử cùng prime → cùng component.

Pseudocode: - Với mỗi x trong nums, phân tích thừa số x. Union x với mỗi thừa số. - Đếm size component.

Code Python 3

from collections import Counter
from typing import List

class DSU:
    def __init__(self): self.par = {}
    def find(self, x):
        if x not in self.par: self.par[x] = x
        while self.par[x] != x:
            self.par[x] = self.par[self.par[x]]
            x = self.par[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra != rb: self.par[ra] = rb


class Solution:
    def largestComponentSize(self, nums: List[int]) -> int:
        dsu = DSU()
        for x in nums:
            d = 2
            v = x
            while d * d <= v:
                if v % d == 0:
                    dsu.union(x, d)
                    while v % d == 0:
                        v //= d
                d += 1
            if v > 1:
                dsu.union(x, v)
        # Đếm: với mỗi phần tử nums (chỉ phần tử nums, không phải prime).
        counter = Counter(dsu.find(x) for x in nums)
        return max(counter.values())

Phân tích độ phức tạp

• Thời gian: O(n · sqrt(max(nums)) · α).
• Bộ nhớ: O(n + max(nums)).

Bình luận

• Trick “union với prime” giảm O(n²) xuống O(n · sqrt(max)).
• Union Find chi tiết hơn ở Chương 24.

Bài tự luyện liên quan

• LC 1101 - The Earliest Moment When Everyone Become Friends.
• LC 1319 - Number of Operations to Make Network Connected.

---

20.6 Distinct Prime Factors of Product in Array (LC 2521)

Đề bài

Cho nums. Trả về số prime factor phân biệt của tích các phần tử.

Ví dụ

Input:  nums = [2, 4, 3, 7, 10, 6]
Output: 4
Giải thích: tích = 2·4·3·7·10·6 = 10080 = 2^5 · 3^2 · 5 · 7. 4 prime phân biệt.

Ràng buộc

• 1 <= len(nums) <= 10^4
• 2 <= nums[i] <= 1000

Clarifying questions

• Số có thể = 1? → 1 không có prime → bỏ qua.
• Tích có overflow? → Không tính tích trực tiếp.

Hướng tiếp cận

Không cần tính tích thực (có thể overflow). Chỉ cần với mỗi số, lấy các thừa số prime, gom hết vào set.

Code Python 3

from typing import List

class Solution:
    def distinctPrimeFactors(self, nums: List[int]) -> int:
        primes: set[int] = set()
        for x in nums:
            d = 2
            while d * d <= x:
                while x % d == 0:
                    primes.add(d)
                    x //= d
                d += 1
            if x > 1:
                primes.add(x)
        return len(primes)

Phân tích độ phức tạp

• Thời gian: O(n · sqrt(max(nums))).
• Bộ nhớ: O(k) với k = số prime phân biệt.

Bình luận

• Bẫy: tính tích trực tiếp → overflow với n lớn. Phân tích từng số là cách an toàn.

Bài tự luyện liên quan

• LC 2417 - Closest Fair Integer.
• LC 1390 - Four Divisors.

Tóm tắt chương & Quyết định

Prime toolbox - chọn theo constraint

n (giới hạn)	Phương pháp	Time
Kiểm tra 1 số n ≤ 10¹²	Trial division đến √n	O(√n)
Đếm primes ≤ n, n ≤ 10⁷	Sieve of Eratosthenes	O(n log log n)
Factor nhiều số ≤ n, n ≤ 10⁶	SPF (Smallest Prime Factor) sieve	precompute O(n log log n), mỗi factor O(log n)
Factor 1 số n ≤ 10¹⁸	Pollard ρ + Miller-Rabin	sub-exponential

Largest Component by Common Factor (LC 952)

• Model: với mỗi số a, union a với mỗi prime factor của nó.
• Sau khi union hết, số DSU root khác nhau cùng prime → cùng component.
• Lưu ý: union giữa số và prime (xem prime như “node ảo”); cuối cùng đếm theo số gốc, không tính prime nodes.

Prime Arrangements (LC 1175) - counting modulo

• Số prime ≤ n: p. Số non-prime: q = n - p.
• Đáp số = p! × q! (mod 10⁹+7).
• Factorial modulo: precompute fact[0..n] mod M, mỗi bước fact[i] = fact[i-1] * i % M.

---