خوارزمية العامل الرئيسي: C، Python مثال

ما هو التخصيم الأولي؟

العامل الرئيسي للمعطى أي وقت الرقم هو العامل الذي هو رقم اولي. العوامل عند ضربها تعطيك رقمًا آخر. العدد الأولي يقبل القسمة على نفسه أو على 1 .

بعبارة أخرى، يتم تحديد العوامل الأولية من خلال العثور على الأعداد الأولية التي تضرب معًا لتكوين العدد الأصلي.

مثال:العوامل الأولية للعدد 10 هي 2 و5. وذلك لأن 2X5 = 10 وكلاهما 2,5 وXNUMX عددان أوليان.

إيجاد العوامل الأولية باستخدام التكرار

لإيجاد العوامل الأولية لرقم معين، نكرر أولاً كل الأرقام من 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 باستخدام التكرار

هذا هو نفس الحل العودي للبايثون ولكنه مكتوب بلغة 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 ليس أوليًا ولا مركبًا.
• يمكن أن يساعد تحليل الأعداد إلى عوامل أولية في حل مشكلات مثل قابلية القسمة، وتبسيط الكسور، وإيجاد قواسم مشتركة بين الكسور المختلفة.
• أيضًا، أحد الاستخدامات المثيرة للتحليل الأولي هو كسر الرموز السرية التي تعتمد على الأرقام.