Buổi 8: Ước, số nguyên tố, UCLN – BCNN

1. Kiến thức chính

Ước và số nguyên tố

• a chia hết cho b khi a % b == 0; khi đó b là ước của a.
• Số nguyên tố có đúng 2 ước là 1 và chính nó: 2, 3, 5, 7, 11, 13, …

Chỉ cần xét đến √n

Ước luôn đi theo cặp: 36 = 1×36 = 2×18 = 3×12 = 4×9 = 6×6. Trong mỗi cặp có một số ≤ √36 = 6. Vì vậy chỉ cần thử i khi i * i <= n.

n = int(input())
nt = n >= 2              # số nhỏ hơn 2 không phải nguyên tố
i = 2
while i * i <= n:
    if n % i == 0:
        nt = False       # tìm thấy ước → không nguyên tố
        break
    i += 1
print("YES" if nt else "NO")

Đếm ước bằng cặp (i, n // i): mỗi ước i ≤ √n cho 2 ước, riêng khi i * i == n chỉ đếm 1.

Tốc độ: bao nhiêu phép tính là kịp?

Python làm được khoảng 10⁶ – 10⁷ phép tính mỗi giây.

UCLN – thuật toán Euclid, BCNN

UCLN(a, b) = UCLN(b, a % b), và UCLN(a, 0) = a.

a, b = map(int, input().split())
x, y = a, b
while y != 0:
    x, y = y, x % y
g = x                     # UCLN
print(g, a // g * b)      # BCNN = a × b ÷ UCLN

Khi đi thi được dùng thư viện: import math rồi math.gcd(a, b), math.lcm(a, b).

2. Ghi nhớ và lỗi thường gặp

3. Câu hỏi tự kiểm tra

1. Số 91 có phải số nguyên tố không?
2. Chạy tay thuật toán Euclid với (60, 24). UCLN bằng bao nhiêu?
3. Muốn kiểm tra số n = 10¹⁰ có nguyên tố không, vòng lặp cần chạy khoảng bao nhiêu lần?

4. Bài tập về nhà

Bài 1 ★★ – DEMNT

Input: hai số nguyên a, b (1 ≤ a ≤ b ≤ 10⁴).

Output: số lượng số nguyên tố trong đoạn từ a đến b.

Bài 2 ★★ – SINHDOI

Hai số nguyên tố hơn kém nhau 2 gọi là cặp số nguyên tố sinh đôi (ví dụ 3 và 5, 11 và 13).

Input: số nguyên n (5 ≤ n ≤ 10⁴).

Output: mỗi dòng một cặp p, p + 2 với p + 2 ≤ n, theo thứ tự tăng dần.

Bài 3 ★★ – UCLNDAY

Input: dòng 1 là n (1 ≤ n ≤ 1000); dòng 2 là n số nguyên dương (≤ 10⁹).

Output: UCLN của cả n số.

Bài 4 ★★★ (thử thách) – TONGUOC

Input: số nguyên n (1 ≤ n ≤ 10¹²).

Output: tổng tất cả các ước của n.