পাইথনে প্রাইম নাম্বার চেক করার বিভিন্ন পদ্ধতি এবং পারফরম্যান্স বিশ্লেষণ

প্রাইম নাম্বার চেক করার তিনটি পদ্ধতি এবং তাদের এক্সিকিউশন টাইম তুলনা করা হলো।

১. সব ডিভাইজার চেক করা (Naive) – O(n)

import time
def check_prime(n):
    if n <= 1: return False
    for d in range(2, n):
        if n % d == 0: return False
    return True

start = time.time()
cnt = sum(check_prime(i) for i in range(1, 10001))
print(f"Primes: {cnt}, Time: {time.time()-start:.4f}s")

আউটপুট

Primes: 1229, Time: 2.31s

২. স্কয়ার রুট পর্যন্ত চেক – O(√n)

import math, time
def is_prime(n):
    if n <= 1: return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0: return False
    return True

start = time.time()
cnt = sum(is_prime(i) for i in range(1, 10001))
print(f"Primes: {cnt}, Time: {time.time()-start:.4f}s")

আউটপুট

Primes: 1229, Time: 0.053s

৩. Sieve of Eratosthenes – O(n log log n)

import time
def sieve(n):
    primes = []
    is_composite = [False] * (n + 1)
    for i in range(2, n + 1):
        if not is_composite[i]:
            primes.append(i)
            for j in range(i*i, n+1, i):
                is_composite[j] = True
    return primes

start = time.time()
primes = sieve(10000)
print(f"Primes: {len(primes)}, Time: {time.time()-start:.4f}s")

আউটপুট

Primes: 1229, Time: ~0.0s

নিষ্কর্ষ: Sieve সবচেয়ে দ্রুত, তারপর স্কয়ার রুট মেথড। naïve পদ্ধতি বড় ইনপুটের জন্য খুব ধীর।