วิธีต่างๆ ในการหาเลขเฉพาะ (Prime Number) ใน Python

เลขเฉพาะ (Prime Number) คือจำนวนเต็มบวกที่หารลงตัวด้วยตัวมันเองและ 1 เท่านั้น (มีตัวหาร 2 ตัว) 1 ไม่ใช่เลขเฉพาะ

วิธีที่ 1: ใช้ For Loop แบบง่าย

def primemethod1(number):
    my_primes = []
    for pr in range(2, number):
        isPrime = True
        for i in range(2, pr):
            if pr % i == 0:
                isPrime = False
        if isPrime:
            my_primes.append(pr)
    print(my_primes)

primemethod1(50)

ผลลัพธ์

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

วิธีที่ 2: For Loop พร้อม Break (เร็วกว่า)

def primemethod2(number):
    my_primes = []
    for pr in range(2, number + 1):
        isPrime = True
        for num in range(2, pr):
            if pr % num == 0:
                isPrime = False
                break  # หยุดลูปทันทีที่เจอตัวหาร
        if isPrime:
            my_primes.append(pr)
    return my_primes

print(primemethod2(50))

วิธีที่ 3: For Loop + Break + Square Root (เร็วที่สุดในกลุ่มนี้)

def primemethod3(number):
    primes = []
    for pr in range(2, number):
        isPrime = True
        # ตรวจสอบแค่ถึงรากที่สองของ pr
        for num in range(2, int(pr ** 0.5) + 1):
            if pr % num == 0:
                isPrime = False
                break
        if isPrime:
            print("Prime number:", pr)

primemethod3(50)

ผลลัพธ์

Prime number: 2
Prime number: 3
Prime number: 5
Prime number: 7
Prime number: 11
Prime number: 13
Prime number: 17
Prime number: 19
Prime number: 23
Prime number: 29
Prime number: 31
Prime number: 37
Prime number: 41
Prime number: 43
Prime number: 47

การเปรียบเทียบประสิทธิภาพ

วิธีเพิ่มเติม: Sieve of Eratosthenes (ประหยัดที่สุดสำหรับหาเยอะ)

def sieve_of_eratosthenes(limit):
    sieve = [True] * (limit + 1)
    sieve[0] = sieve[1] = False
    
    for i in range(2, int(limit**0.5) + 1):
        if sieve[i]:
            for j in range(i*i, limit + 1, i):
                sieve[j] = False
    
    return [i for i, is_prime in enumerate(sieve) if is_prime]

print(sieve_of_eratosthenes(50))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

สรุป: วิธีที่ 3 ดีที่สุดสำหรับตรวจสอบเลขเดี่ยว Sieve ดีที่สุดสำหรับหาเลขเฉพาะทั้งช่วง