प्राइम फैक्टर एल्गोरिथ्म: सी, Python उदाहरण

अभाज्य गुणनखंडन क्या है?

किसी दिए गए गुणनखंड का अभाज्य गुणनखंड कोई संख्या वह कारक है जो एक है प्रधान संख्यागुणनखंडों को गुणा करने पर आपको एक और संख्या प्राप्त होती है। एक अभाज्य संख्या स्वयं या 1 से विभाज्य होती है।

दूसरे शब्दों में, अभाज्य गुणनखंडों का निर्धारण यह पता लगाकर किया जाता है कि कौन सी अभाज्य संख्याएं आपस में गुणा करके मूल संख्या बनाती हैं।

उदाहरण: 10 के अभाज्य गुणनखंड 2 और 5 हैं। ऐसा इसलिए है क्योंकि 2X5 =10 है और 2,5 दोनों अभाज्य संख्याएँ हैं।

पुनरावृत्ति का उपयोग करके अभाज्य गुणनखंड ज्ञात करना

किसी दी गई संख्या के अभाज्य गुणनखंड ज्ञात करने के लिए, हम सबसे पहले 2 से लेकर संख्या के वर्गमूल तक सभी संख्याओं को दोहराते हैं, और फिर जाँचते हैं कि क्या प्रत्येक संख्या अभाज्य है। जब तक मूल संख्या इस अभाज्य संख्या से विभाज्य है, हम प्रत्येक पुनरावृत्ति के साथ इस अभाज्य संख्या को जोड़ते रहते हैं।

उदाहरण:

40 से बड़ी प्रत्येक अभाज्य संख्या को निम्नलिखित सूत्र में लिखा जाता है: n²+n+41. इसलिए, हम n को सभी संख्याओं के साथ प्रतिस्थापित करके संगत अभाज्य गुणनखंड ज्ञात कर सकते हैं। उदाहरण के लिए, 0²+0+41=41, 1²+1+41=43, 2²+2+41=47,…

किसी संख्या का अभाज्य गुणनखंड कैसे प्रिंट करें?

• इस विधि में, हम 2 से लेकर संख्या के वर्गमूल तक की संख्याओं पर पुनरावृत्ति करेंगे, जैसा कि पिछले अनुभाग में बताया गया है।
• इसके लिए हमें 2 से लेकर n के वर्गमूल तक प्रत्येक संख्या पर मूल संख्या के मापांक की जांच करनी होगी।
• फिर, हम उन अभाज्य संख्याओं की सूची ज्ञात करते हैं जो n के गुणनखंड हैं।
• यह समाधान O(Sqrt(n)) समय जटिलता में है।

कलन विधि:

Set a counter i  to 2
While i  <= sqrt(n):
	While n% i  == 0:
		n = n / i  
		print i  
	i  = i  +1
if n > 1:
	print n

छलनी एल्गोरिथ्म

छलनी विधि संख्याओं के सबसे छोटे अभाज्य गुणनखंड को संग्रहीत करने पर निर्भर करती है, जो किसी भी संख्या के अभाज्य गुणनखंडों की गणना करते समय जटिलता को काफी हद तक कम कर देती है। छलनी एल्गोरिथ्म सभी अभाज्य गुणनखंडों को कुछ हद तक कुशलता से ढूँढ़ लेता है।

• इस एल्गोरिथ्म की मुख्य अवधारणा प्रत्येक संख्या के सबसे छोटे अभाज्य गुणनखंड को अधिकतम संख्या तक संग्रहीत करना है।
• हम प्रत्येक दी गई संख्या के लिए सबसे छोटा अभाज्य अंक लेते हैं और उसे अभाज्य गुणनखंडों के समूह में जोड़ते हैं।
• अंत में, हम इस अभाज्य संख्या से भाग देते हैं और इन चरणों को तब तक दोहराते हैं जब तक हम 1 तक नहीं पहुंच जाते।
• यह सब O(log(n)) समय जटिलता में किया जाता है, जिससे समाधान की दक्षता में काफी सुधार होता है।
• इससे उन बहुत बड़ी संख्याओं के अभाज्य गुणनखंडों की गणना करना संभव हो जाता है, जिन्हें हम पिछली विधि का प्रयोग करके निकाल सकते थे।

उदाहरण:

दूसरा तरीका यह जांचना है कि क्या संख्या को 6n-1 या 6n+1 के रूप में लिखा जा सकता है क्योंकि 2 और 3 के अलावा किसी भी अन्य अभाज्य संख्या को दो सूत्रों में से एक में लिखा जाना चाहिए। उदाहरण के लिए, 5=6(1)-1, 19=6(3)+1,…।

कलन विधि:

प्रत्येक संख्या के सबसे छोटे अभाज्य गुणनखंड को प्रत्येक तत्व के लिए प्रारंभिक मान के रूप में सूचकांक मान के साथ संग्रहीत करने के लिए एक सारणी सारणी को परिभाषित करें सरणी.

Set array[1] to 1
Set i to 2
While i*i > max number:
	If array[i] == i:
		Set j to i*i
		While j > max number:
			If array[j] == j:
				Array[j] = i
			j = j + i
	i = i + 1
while the number != 1:
	print array[the number]
	the number = the number / array[the number]

Python पुनरावृत्ति का उपयोग करके अभाज्य गुणनखंड

यहाँ, हम एक कोड दिखाएंगे Python पुनरावृत्त विधि में किसी दी गई संख्या के अभाज्य गुणनखंड ज्ञात करने की भाषा:

import math
def PrimeFactors(n):
    for i in range(2,int(math.sqrt(n))+1,1):
        while n%i==0:#find all the occurrences of a prime factor
            print((int)(i)),
            n=n/i
    if n!=1:#if the number was originally a prime
        print((int)(n))
n=(int)(input("Enter the number you want: "))
PrimeFactors(n)

आउटपुट:

Enter the number you want: 4
4

Python रिकर्सन का उपयोग करके अभाज्य गुणनखंड

यह अनुभाग एक कोड दिखाता है Python भाषा किसी दी गई संख्या के अभाज्य गुणनखंड ज्ञात करने के लिए छलनी विधि का उपयोग करना।

import math
High = (int)(1e5+7)
array=[0 for i in range(High)]
# function to generate all the smallest prime 
def Sieve():
#factors of the numbers until the maximum  number
    for i in range(1, High):
        array[i]=i
    for i in range(2, math.ceil(math.sqrt(High))):
        if (array[i] == i):
            for j in range(i*i, High,i):
                if(array[j]==j):
                    array[j]=i
def PrimeFactors(n):
#We will keep dividing until we reach 1
    if n == 1:
        return
    print((int)(array[n]))
    PrimeFactors((int)(n/array[n]))
#Here we call the function after dividing it by this prime
Sieve()
n=(int)(input("Enter the number you want: "))
PrimeFactors(n)

आउटपुट:

Enter the number you want: 4
2
2

C पुनरावृत्ति का उपयोग करके अभाज्य गुणनखंड कार्यक्रम

यह पुनरावृत्त पायथन के समान ही समाधान है, लेकिन इसमें लिखा गया है सी भाषा.

हम उपयोगकर्ता से संख्या दर्ज करने के लिए कहते हैं, फिर 2 से लेकर इस संख्या के वर्गमूल तक प्रत्येक संख्या के लिए, हमें इस कारक की सभी घटनाओं को प्रिंट करके यह जांचना होता है कि क्या यह विभाज्य है।

#include <stdio.h>
int main()
{
    int n;
    printf("Enter the number you want: ");
    scanf("%d", &n);
    for(int i=2; i*i<=n; i++)
    {
        while(n%i==0)//find all the occurrences of a prime factor
        {
            printf("%d\n",i);
            n/=i;
        }
    }
    if(n!=1)//if the number was originally a prime
    {
        printf("%d",n);
    }
    return 0;
}

आउटपुट:

Enter the number you want: 2
2

सी प्राइम फैक्टर प्रोग्राम रिकर्सन का उपयोग करके

यह पायथन रिकर्सिव समाधान जैसा ही है, लेकिन C में लिखा गया है।

हम उपयोगकर्ता से संख्या दर्ज करने के लिए कह सकते हैं; फिर, हम प्राइम्स ऐरे बनाते हैं जो प्रत्येक संख्या के सबसे छोटे प्राइम फैक्टर को संग्रहीत करता है। अंत में, हम प्राइम फैक्टर्स रिकर्सिव फ़ंक्शन को कॉल करते हैं, जो दी गई संख्या को उसके सबसे छोटे प्राइम फैक्टर से विभाजित करता है और एक तक पहुंचने तक खुद को याद करता है।

#include <stdio.h>
int Max = 100007;
int array[100007];
void Sieve()//helping function to generate all the smallest //prime factors of the numbers until the maximum number
{
    for(int i=1;i<Max;i++)
    {
        array[i]=i;
    }
    for(int i=2;i*i<=Max;i++)
    {
        if(array[i]==i)
        {
            for(int j=i*i;j<Max;j+=i)
            {
                if(array[j]==j)
                {
                    array[j]=i;
                }
            }
        }
    }
}
void PrimeFactors(int n)
{
    if(n==1)//keep dividing until we reach 1
    {
        return;
    }
    printf("%d\n",array[n]);
    PrimeFactors(n/array[n]);//call the function after dividing by //this prime
}
int main()
{
    Sieve();
    int n;
    printf("Enter the number you want: ");
    scanf("%d", &n);
    PrimeFactors(n);
    return 0;
}

आउटपुट:

Enter the number you want: 2
2

अभाज्य संख्याओं के बारे में कुछ रोचक तथ्य

• सबसे दिलचस्प तथ्यों में से एक यह है कि 2 के अलावा कोई भी सम संख्या दो अभाज्य संख्याओं का योग हो सकती है।
• उदाहरण के लिए: 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3… आदि।
• एक अन्य तथ्य यह है कि 2 और 3 के अलावा कोई भी क्रमागत अभाज्य संख्या नहीं है, क्योंकि एकमात्र सम अभाज्य संख्या 2 ही है।
• इसके अलावा, 2 और 3 को छोड़कर सभी अभाज्य संख्याओं को निम्नलिखित रूप में लिखा जा सकता है: 6 * n + 1 या 6 * n – 1, जहाँ n एक धनात्मक पूर्णांक है।
• किसी संख्या के अभाज्य गुणनखंडों का समुच्चय अद्वितीय होता है।
• संख्या 1 न तो अभाज्य है और न ही भाज्य।
• संख्याओं के अभाज्य गुणनखंडन से विभाज्यता, भिन्नों को सरल बनाने, तथा भिन्न भिन्नों के उभयनिष्ठ हर ज्ञात करने जैसी समस्याओं को हल करने में सहायता मिल सकती है।
• इसके अलावा, अभाज्य गुणनखंडन का एक रोमांचक उपयोग संख्या आधारित गुप्त कोड को तोड़ना भी है।