📚 Định nghĩa Số Nguyên tố

Số nguyên tố là số tự nhiên lớn hơn 1, chỉ có đúng 2 ước số là 1 và chính nó.

🔍 Các tính chất:

  • Số 2: Là số nguyên tố nhỏ nhất và duy nhất chẵn
  • Số lẻ: Tất cả số nguyên tố khác đều là số lẻ
  • Ước số: Chỉ có đúng 2 ước: 1 và chính nó
  • Vô hạn: Có vô số số nguyên tố (chứng minh của Euclid)

💡 Phân biệt:

Loại số
Định nghĩa
Ví dụ
Số nguyên tố
Có đúng 2 ước số
2, 3, 5, 7, 11, 13...
Hợp số
Có nhiều hơn 2 ước số
4, 6, 8, 9, 10, 12...
Số đặc biệt
Không thuộc 2 loại trên
0, 1

⚙️ Thuật toán Kiểm tra Số Nguyên tố

🎯 Thuật toán Cơ bản:

  1. Nếu n ≤ 1: Không phải số nguyên tố
  2. Nếu n = 2: Là số nguyên tố
  3. Nếu n chẵn: Không phải số nguyên tố
  4. Kiểm tra chia hết cho các số lẻ từ 3 đến √n
  5. Nếu không chia hết cho số nào: Là số nguyên tố

🚀 Tối ưu hóa √n:

Tại sao chỉ cần kiểm tra đến √n?

Nếu n có ước a > √n, thì phải tồn tại ước b = n/a < √n

Ví dụ: n = 36, √36 = 6

  • Ước 9 > 6 ⟹ tồn tại ước 4 = 36/9 < 6
  • Ước 12 > 6 ⟹ tồn tại ước 3 = 36/12 < 6

📊 Độ phức tạp:

Thuật toán cơ bản: O(n)

Thuật toán tối ưu: O(√n)

Cải tiến thêm: Chỉ kiểm tra số lẻ ⟹ O(√n/2)

🐍 Code Python

📝 Phiên bản cơ bản:

basic_prime_check.py 
def is_prime_basic(n):
    """
    Kiểm tra số nguyên tố - Phiên bản cơ bản
    Độ phức tạp: O(n)
    """
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    # Kiểm tra chia hết cho các số từ 3 đến n-1
    for i in range(3, n, 2):
        if n % i == 0:
            return False
    
    return True

# Ví dụ sử dụng
number = int(input("Nhập số cần kiểm tra: "))
if is_prime_basic(number):
    print(f"{number} là số nguyên tố")
else:
    print(f"{number} không phải số nguyên tố")

⚡ Phiên bản tối ưu:

optimized_prime_check.py 
import math

def is_prime_optimized(n):
    """
    Kiểm tra số nguyên tố - Phiên bản tối ưu
    Độ phức tạp: O(√n)
    """
    if n <= 1:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    # Chỉ kiểm tra đến √n
    limit = int(math.sqrt(n)) + 1
    for i in range(3, limit, 2):
        if n % i == 0:
            return False
    
    return True

# Test với nhiều số
test_numbers = [2, 3, 4, 17, 25, 97, 100, 101]
for num in test_numbers:
    result = is_prime_optimized(num)
    print(f"{num}: {'Nguyên tố' if result else 'Không nguyên tố'}")

🔍 Phiên bản có log chi tiết:

detailed_prime_check.py 
import math
import time

def is_prime_detailed(n):
    """
    Kiểm tra số nguyên tố với log chi tiết
    """
    print(f"\n🔍 Kiểm tra số {n}:")
    print("-" * 30)
    
    start_time = time.time()
    
    # Kiểm tra các trường hợp đặc biệt
    if n <= 1:
        print(f"❌ {n} ≤ 1, không phải số nguyên tố")
        return False
    
    if n == 2:
        print("✅ Số 2 là số nguyên tố duy nhất chẵn")
        return True
    
    if n % 2 == 0:
        print(f"❌ {n} là số chẵn, không phải số nguyên tố")
        return False
    
    # Tính giới hạn
    limit = int(math.sqrt(n)) + 1
    print(f"📐 √{n} ≈ {math.sqrt(n):.2f}")
    print(f"🎯 Kiểm tra từ 3 đến {limit-1}")
    
    # Kiểm tra các ước
    for i in range(3, limit, 2):
        if n % i == 0:
            print(f"❌ {n} ÷ {i} = {n//i} (dư {n%i})")
            print(f"   Tìm thấy ước: {n} = {i} × {n//i}")
            return False
        print(f"✓ {n} ÷ {i} = {n//i} (dư {n%i})")
    
    end_time = time.time()
    print(f"✅ {n} là số nguyên tố!")
    print(f"⏱️ Thời gian: {(end_time - start_time)*1000:.3f} ms")
    return True

# Sử dụng
number = int(input("Nhập số cần kiểm tra: "))
is_prime_detailed(number)

📋 Ví dụ Minh họa

✅ Ví dụ số nguyên tố:

Kiểm tra số 17:
  • √17 ≈ 4.12 → Kiểm tra đến 4
  • 17 ÷ 3 = 5 dư 2 ✓
  • Không có ước nào → 17 là số nguyên tố
Kiểm tra số 29:
  • √29 ≈ 5.39 → Kiểm tra đến 5
  • 29 ÷ 3 = 9 dư 2 ✓
  • 29 ÷ 5 = 5 dư 4 ✓
  • Không có ước nào → 29 là số nguyên tố

❌ Ví dụ hợp số:

Kiểm tra số 15:
  • √15 ≈ 3.87 → Kiểm tra đến 3
  • 15 ÷ 3 = 5 dư 0 ❌
  • Tìm thấy ước: 15 = 3 × 5 → 15 không phải số nguyên tố
Kiểm tra số 21:
  • √21 ≈ 4.58 → Kiểm tra đến 4
  • 21 ÷ 3 = 7 dư 0 ❌
  • Tìm thấy ước: 21 = 3 × 7 → 21 không phải số nguyên tố

📊 Bảng số nguyên tố đầu tiên:

STT
Số nguyên tố
STT
Số nguyên tố
1
2
11
31
2
3
12
37
3
5
13
41
4
7
14
43
5
11
15
47
6
13
16
53
7
17
17
59
8
19
18
61
9
23
19
67
10
29
20
71

📝 Nhật ký các bước thực hiện

Nhật ký sẽ hiển thị ở đây sau khi bạn kiểm tra một số...