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

Số nguyên tố là số lớn hơn 1 chỉ chia hết cho 1 và chính nó. Thuật toán: đếm số ước, nếu đúng 2 ước (1 và n) thì là số nguyên tố.

Thuật toán:

int count = 0;
for (int i = 1; i <= n; i++)
{
    if (n % i == 0) count++;
}
bool isPrime = (count == 2);

Tối ưu: Chỉ cần kiểm tra đến sqrt(n), bỏ qua số chẵn (trừ 2).

Ví dụ

using System;

namespace Demo
{
    class MyApplication
    {
        public static void Main()
        {
            int n = 17, count = 0;
            
            for (int i = 1; i <= n; i++)
            {
                if (n % i == 0) count++;
            }
            
            if (count == 2)
                Console.WriteLine("{0}: Prime Number", n);
            else
                Console.WriteLine("{0}: Not a Prime Number", n);
            
            Console.ReadLine();
        }
    }
}

Kết quả

17: Prime Number

Phiên bản tối ưu (O(√n)):

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