Chương trình C# kiểm tra số nguyên tố (Prime Number)

Số nguyên tố (prime) là số nguyên dương > 1 chỉ có 2 ước số: 1 và chính nó. Kiểm tra bằng cách thử chia từ 2 đến √n.

Mã nguồn (cách gốc: đếm ước số)

using System;

namespace Demo {
    class MyApplication {
        public static void Main() {
            int n = 5;
            int divisorCount = 0;
            
            for (int i = 1; i <= n; i++) {
                if (n % i == 0) divisorCount++;
            }
            
            if (divisorCount == 2) {
                Console.WriteLine("{0} là số nguyên tố", n);
            } else {
                Console.WriteLine("Không phải số nguyên tố");
            }
            Console.ReadLine();
        }
    }
}

Kết quả

5 là số nguyên tố

Cách tối ưu: Chỉ kiểm tra đến √n (O(√n))

static bool IsPrime(int n) {
    if (n <= 1) return false;
    if (n <= 3) return true;     // 2, 3 là nguyên tố
    if (n % 2 == 0 || n % 3 == 0) return false; // Loại bội của 2, 3
    
    // Kiểm tra dạng 6k ± 1 đến sqrt(n)
    for (int i = 5; i * i <= n; i += 6) {
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    }
    return true;
}

Giải thích tối ưu 6k ± 1

• Mọi số nguyên > 3 đều viết dạng: 6k, 6k±1, 6k+2, 6k+3, 6k+4.
• 6k, 6k+2, 6k+4 chia hết 2; 6k+3 chia hết 3 → không phải nguyên tố.
• Chỉ cần kiểm tra 6k-1 và 6k+1 (tức i và i+2 với i=5,11,17...).

Sàng Eratosthenes (tìm tất cả nguyên tố ≤ N)

static List Sieve(int n) {
    bool[] isPrime = new bool[n + 1];
    for (int i = 2; i <= n; i++) isPrime[i] = true;
    
    for (int p = 2; p * p <= n; p++) {
        if (isPrime[p]) {
            for (int i = p * p; i <= n; i += p)
                isPrime[i] = false;
        }
    }
    
    var primes = new List();
    for (int i = 2; i <= n; i++) if (isPrime[i]) primes.Add(i);
    return primes;
}

Lưu ý

• Code gốc duyệt 1..n (O(n)) — chậm với n lớn. Cách √n nhanh hơn nhiều.
• Số 1 KHÔNG phải số nguyên tố.
• Với số lớn (BigInteger), dùng Miller-Rabin probabilistic test.