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

Giả sử chúng ta có một số n, chúng ta phải tạo một danh sách tất cả các số nguyên tố nhỏ hơn số nguyên tố bằng nhau đến n theo thứ tự tăng dần. Chúng ta phải ghi nhớ rằng 1 không phải là số nguyên tố.

Vì vậy, nếu đầu vào là 12, thì đầu ra sẽ là [2, 3, 5, 7, 11].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• sàng:=danh sách có kích thước n + 1 và điền bằng True
• số nguyên tố:=một danh sách mới, ban đầu để trống
• đối với tôi trong phạm vi từ 2 đến n, thực hiện
  • nếu sieve [i] là True, thì
    • chèn i vào cuối các số nguyên tố
    • cho j trong phạm vi từ i đến n, cập nhật từng bước theo i, thực hiện
      • sàng [j]:=Sai
• trả về số nguyên tố

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

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]