Số nguyên tố

Số nguyên tố là gì

Số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có nhất 2 ước là 1 và chính nó. Dựa trên định nghĩa này ta có thuật toán tìm số nguyên tố một cách tự nhiên nhất như sau. Với Python:

def prime(a):
    if a < 2: return False
    else:
        for i in range(2, a):
            if (a % i == 0):
                return False
    else: return True

Tối ưu hóa:

Nhìn vào thuật toán trên, dường như với những số bé thì sẽ không có vấn đề gì. Tuy nhiên, nếu áp dụng với những số lớn cỡ 1 triệu thì sao nhỉ. Ồ!!! thật vất vả phải không? Bây giờ nếu ta chỉ xét i đến căn bậc 2 của a thì sao nhỉ? Tuyệt !!! Thay vì lặp 1 triệu vòng, ta chỉ cần lặp 1000 vòng.

import math
def prime(a):
    if a < 2: return False
    else:
        for i in range(2, int(sqrt(a)) + 1):
            if (a % i == 0):
                return False
    else: return True

Sàng số nguyên tố:

Một bài toán từ hồi tôi còn học lớp 6, sàng Eratosthenes. Đến nay, với python chưa bao giờ dễ dàng và ngắn gọn đến vậy.

def Eratosthenes(a):
    return [i for i in range(2, a + 1) if prime(i) == True]

Với python, số nguyên tố thật tuyệt vời phải không nào. Have fun with