วิธีการหาจำนวนเฉพาะ (Prime Numbers) ใน C#

จำนวนเฉพาะ (Prime Number) คือ จำนวนเต็มบวกที่มากกว่า 1 และมีตัวประกอบเพียง 1 และตัวมันเอง มีหลายวิธีการตรวจสอบใน C#

วิธี 1: ใช้ For Loop (Basic)

using System;

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

วิธี 2: ใช้ Function (แยก Logic)

using System;

namespace Program
{
    class Demo
    {
        static void Main(string[] args)
        {
            int n = 7;
            int result = IsPrime(n);
            
            if (result == 1)
                Console.WriteLine("Prime number");
            else
                Console.WriteLine("Not a prime number");
            
            Console.Read();
        }
        
        private static int IsPrime(int n)
        {
            if (n <= 1) return 0;
            if (n == 2) return 1;
            if (n % 2 == 0) return 0;
            
            for (int i = 3; i * i <= n; i += 2) // ตรวจสอบเฉพาะคี่ จนถึง √n
            {
                if (n % i == 0)
                    return 0;
            }
            return 1;
        }
    }
}

ผลลัพธ์

Prime number

การเพิ่มประสิทธิภาพ (Optimization)

Sieve of Eratosthenes (หา Prime ทั้งช่วง)

public static List<int> GetPrimes(int max)
{
    bool[] isPrime = new bool[max + 1];
    for (int i = 2; i <= max; i++) isPrime[i] = true;
    
    for (int i = 2; i * i <= max; i++)
    {
        if (isPrime[i])
        {
            for (int j = i * i; j <= max; j += i)
                isPrime[j] = false;
        }
    }
    
    return Enumerable.Range(2, max - 1).Where(i => isPrime[i]).ToList();
}