Tạo danh sách số nguyên tố nhỏ hơn n trong Python

Cho số n, tạo danh sách tất cả số nguyên tố <= n theo thứ tự tăng dần. Lưu ý 1 không phải số nguyên tố.

Ví dụ, 12 -> [2, 3, 5, 7, 11].

Các bước giải quyết (sàng Eratosthenes):

• sieve := danh sách kích thước n+1 giá trị True.
• primes := danh sách rỗng.
• Với i từ 2 đến n:
  • Nếu sieve[i] là True:
    • Thêm i vào primes.
    • Với j từ i đến n, bước i: sieve[j] = False.
• Trả về primes.

Ví dụ minh họa

class Solution:
    def solve(self, n):
        sieve = [True] * (n + 1)
        primes = []
        for i in range(2, n + 1):
            if sieve[i]:
                primes.append(i)
                for j in range(i, n + 1, i):
                    sieve[j] = False
        return primes

ob = Solution()
print(ob.solve(12))

Đầu vào

12

Đầu ra

[2, 3, 5, 7, 11]