Python-এ দেওয়া সংখ্যা ইউক্লিড নম্বর (Euclid Number) কিনা যাচাই করা

মান লেন, আমাদের কাছে একটি সংখ্যা n আছে। আমাদের যাচাই করতে হবে n ইউক্লিড নম্বর কিনা। ইউক্লিড নম্বর হল এমন পূর্ণসংখ্যা যা নিচের রূপে রিপ্রেজেন্ট করা যায়:

n = P_n + 1

যেখানে P_n হল প্রথম n টি প্রাইম সংখ্যার গুণফল।

যেমন, ইনপুট হলে n = 211, তবে আউটপুট হবে True কারণ 211 = (2×3×5×7) + 1।

এটি সমাধান করতে আমরা নিচের ধাপগুলো অনুসরণ করব:

MAX := 10000
primes := একটি নতুন লিস্ট।
generate_all_primes() ফাংশন সংজ্ঞায়িত করুন।
prime := MAX সাইজের লিস্ট True দিয়ে ফিল করা।
x := 2
যখন x * x < MAX, তখন লুপ চালান:
- যদি prime[x] True হয়, তবে i কে x*2 থেকে MAX পর্যন্ত x করে বাড়িয়ে prime[i] := False করুন।
- x := x + 1
x কে 2 থেকে MAX-1 পর্যন্ত লুপ চালান:
- যদি prime[x] true হয়, তবে primes-এ x অ্যাপেন্ড করুন।
মূল মেথড থেকে:
- generate_all_primes() কল করুন।
- mul := 1, i := 0
- যখন mul < n, তখন লুপ চালান:
  - mul := mul * primes[i]
  - যদি mul + 1 == n হয়, তবে True রিটার্ন করুন।
  - i := i + 1
- False রিটার্ন করুন।

উদাহরণ কোড

MAX = 10000
primes = []

def generate_all_primes():
    prime = [True] * MAX
    x = 2
    while x * x < MAX:
        if prime[x] == True:
            for i in range(x * 2, MAX, x):
                prime[i] = False
        x += 1
    for x in range(2, MAX):
        if prime[x]:
            primes.append(x)

def solve(n):
    generate_all_primes()
    mul = 1
    i = 0
    while mul < n:
        mul = mul * primes[i]
        if mul + 1 == n:
            return True
        i += 1
    return False

n = 211
print(solve(n))

ইনপুট

আউটপুট

True