পাইথনে প্রাইম নম্বর খুঁজে বের করার বিভিন্ন পদ্ধতি

প্রাইম নম্বর কী?

১-র চেয়ে বড় একটি পূর্ণসংখ্যা যা শুধু ১ এবং নিজের দ্বারা বিভাজ্য। ১ প্রাইম নয়।

পদ্ধতি ১: নেস্টেড ফর লুপ (নেভি)

def prime_method1(n):
    primes = []
    for num in range(2, n):
        is_prime = True
        for i in range(2, num):
            if num % i == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(num)
    return primes

print(prime_method1(50))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

সময় জটিলতা: O(n²) — বড় n-এ ধীর।

পদ্ধতি ২: ব্রেক সহ অপ্টিমাইজড

def prime_method2(n):
    primes = []
    for num in range(2, n + 1):
        is_prime = True
        for i in range(2, num):
            if num % i == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(num)
    return primes

print(prime_method2(50))

ব্রেক দিয়ে অপ্রয়োজনীয় ইটারেশন কমানো হয়েছে।

পদ্ধতি ৩: স্কয়ার রুট অপ্টিমাইজেশন (সবচেয়ে কার্যকর নেভি)

def prime_method3(n):
    primes = []
    for num in range(2, n):
        is_prime = True
        # শুধু sqrt(num) পর্যন্ত চেক করলেই হয়
        for i in range(2, int(num ** 0.5) + 1):
            if num % i == 0:
                is_prime = False
                break
        if is_prime:
            primes.append(num)
    return primes

print(prime_method3(50))

কারণ: যদি a × b = num হয়, তবে those numbers sqrt(num)-এর একপাশে থাকবে।

পদ্ধতি ৪: Sieve of Eratosthenes (সর্বোত্তম বড় n-এ)

def sieve_of_eratosthenes(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    
    for i in range(2, int(n ** 0.5) + 1):
        if is_prime[i]:
            for j in range(i * i, n + 1, i):
                is_prime[j] = False
    
    return [i for i, prime in enumerate(is_prime) if prime]

print(sieve_of_eratosthenes(50))
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

সময় জটিলতা: O(n log log n) — অনেক দ্রুত।

পদ্ধতি ৫: পাইথন এক-লাইনার (ফাংশনাল)

# ফিল্টার + ল্যাম্বডা
primes = list(filter(lambda x: all(x % i != 0 for i in range(2, int(x**0.5)+1)), range(2, 50)))
print(primes)

পারফরম্যান্স তুলনা (n=100,000)

সুপারিশ

• ছোট n (< ১০০০): পদ্ধতি ৩ যথেষ্ট।
• বড় n (> ১০০০০): Sieve of Eratosthenes বাধ্যতামূলক।
• বারবার প্রাইম চেক করতে: প্রি-কম্পিউটেড সেট বা sympy.isprime() ব্যবহার করুন।