पायथन में अभाज्य संख्याएं गिनें

मान लीजिए हमारे पास एक सीमा n है। हमें 2 से n की सीमा में मौजूद अभाज्य संख्याओं की गिनती करनी है। यदि n = 10, तो परिणाम 4 होगा। क्योंकि 10 से पहले चार अभाज्य संख्याएं हैं, वे हैं 2, 3, 5, 7।

इसे हल करने के लिए हम इस दृष्टिकोण का पालन करेंगे:

• count = 0
• prime = आकार n + 1 की एक सरणी लें, और इसे False से भरें
• i = 0 से n तक, करें
  • यदि prime[i] = false, तो
    • count को 1 से बढ़ाएं
    • j = 2 सेट करें
    • जब तक j * i < n, तब
      • prime[i * j] = True
      • j = j + 1
• count वापस करें

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

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))

इनपुट

n = 50 n = 10

आउटपुट

15 4