मान लीजिए हमारे पास एक संख्या n है। हमें जांचना है कि n यूक्लिड नंबर है या नहीं। जैसा कि हम जानते हैं यूक्लिड संख्याएं पूर्णांक हैं जिन्हें इस रूप में दर्शाया जा सकता है:
n= Pn+1
जहां पहले n अभाज्य संख्याओं का गुणनफल है।
तो, यदि इनपुट n = 211 जैसा है, तो आउटपुट True होगा n को इस रूप में दर्शाया जा सकता है:
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
- i के लिए रेंज x * 2 से MAX तक, प्रत्येक चरण में x से अपडेट करें, करें
- यदि prime[x] True है, तो
- x के लिए रेंज 2 से MAX - 1 तक, करें
- यदि prime[x] true है, तो
- primes के अंत में x डालें
- यदि prime[x] true है, तो
- मुख्य विधि से निम्नलिखित करें:
- 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))
इनपुट
211
आउटपुट
True
