Đếm số nguyên tố trong Python

Giả sử chúng ta có giới hạn n. Chúng ta phải đếm số lượng các số nguyên tố có trong phạm vi từ 2 đến n. Vì vậy, nếu n =10, kết quả sẽ là 4. Vì có bốn số nguyên tố đứng trước 10, chúng là 2, 3, 5, 7.

Để giải quyết vấn đề này, chúng tôi sẽ thực hiện theo cách tiếp cận này -

• count =0
• lấy một mảng số nguyên tố =có kích thước n + 1 và điền nó bằng Sai
• for i =0 to n, do
  • nếu số nguyên tố [i] =false, thì
    • tăng số lượng lên 1
    • đặt j =2
    • while j * i
    • prime [i * j] =True
    • j =j + 1

Ví dụ

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

class Solution(object):
   def countPrimes(self, n):
      """
      :type n: int
      :rtype: int
      """
      count = 0
      primes = [False for i in range(n+1)]
      for i in range(2,n):
         if primes[i] == False:
            count+=1
            j = 2
            while j*i<n:
               primes[j*i] = True
               j+=1
      return count
ob1 = Solution()
print(ob1.countPrimes(50))
print(ob1.countPrimes(10))

Đầu vào

n = 50
n = 10

Đầu ra

15
4