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

Cho giới hạn n. Đếm số nguyên tố từ 2 đến n. Ví dụ: n=10 → 4 (2,3,5,7).

Giải pháp

Sàng Eratosthenes:

• count = 0, mảng prime kích thước n+1 khởi tạo False.
• Duyệt i từ 2 đến n-1: nếu prime[i] == False → count++, j=2, while j*i < n: prime[j*i]=True, j++.
• Trả về count.

Ví dụ

Triển khai Python:

class Solution(object): 
    def countPrimes(self, n): 
        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