পাইথনে প্রাইম নাম্বার গণনা (Count Primes)

একটি লিমিট n দেওয়া থাকে। ২ থেকে n পর্যন্ত কতটি প্রাইম নাম্বার আছে তা গণনা করতে হবে। এরাস্থেনিস ছাঁনি (Sieve of Eratosthenes) অ্যালগরিদম ব্যবহার করা হয়েছে।

সমাধানের পদ্ধতি

1. count = 0, primes বুলিয়ান অ্যারে (সাইজ n+1) ফলস দিয়ে ইনিশিয়ালাইজ করুন।
2. for i in range(2, n):
   • যদি primes[i] == False:
     • count++।
     • j = 2 থেকে j*i < n পর্যন্ত primes[j*i] = True।
3. count রিটার্ন করুন।

উদাহরণ কোড

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

ইনপুট

n = 50 n = 10

আউটপুট

15 4