पायथन में प्राइम्स की गणना करें

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

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

• गिनती =0
• एक सरणी प्राइम =आकार n + 1 लें, और इसे गलत से भरें
• i =0 से n के लिए, करें
  • अगर अभाज्य[i] =असत्य, तो
    • गणना में 1 की वृद्धि करें
    • सेट जे =2
    • जबकि j* i
    • प्राइम[i * j] =सच
    • जे =जे + 1

उदाहरण

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

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