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

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

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

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

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

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

للعثور على العوامل الأولية لعدد معين، نقوم أولاً بالتكرار على جميع الأرقام من 2 حتى الجذر التربيعي للرقم، ثم نتحقق مما إذا كان كل رقم أوليًا. طالما أن الرقم الأصلي قابل للقسمة على هذا العدد الأولي، فإننا نستمر في إضافة هذا العدد الأولي مع كل تكرار.

على سبيل المثال:

كل عدد أولي أكبر من 40 يتم كتابته في الصفحة التاليةwing الصيغة: ن2+ن+41. لذا، يمكننا التعويض بـ n بجميع الأرقام لإيجاد العامل الأولي المقابل. على سبيل المثال، 02+0+41=41, 12+1+41=43, 22+2+41=47،...

كيفية طباعة العامل الرئيسي لعدد؟

  • في هذه الطريقة، سنقوم بتكرار الأرقام من 2 حتى الجذر التربيعي للرقم، كما ذكرنا في القسم السابق.
  • لذلك، نحتاج إلى التحقق من معامل الرقم الأصلي على كل رقم من 2 حتى الجذر التربيعي لـ n.
  • ثم نجد قائمة الأعداد الأولية التي هي من عوامل n.
  • هذا الحل موجود في زمن O(Sqrt(n)) complexإيتي.

الخوارزمية:

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

خوارزمية الغربال

تعتمد طريقة الغربلة على تخزين أصغر عامل أولي من الأرقام، مما يقلل من complexيمكن ملاحظته عند حساب العوامل الأولية لأي رقم. تجد خوارزمية الغربال جميع العوامل الأولية بكفاءة إلى حد ما.

  • المفهوم الرئيسي لهذه الخوارزمية هو تخزين أصغر عامل أولي لكل رقم حتى الحد الأقصى للعدد.
  • نأخذ أصغر عدد أولي لكل رقم ونضيفه إلى مجموعة العوامل الأولية.
  • وأخيراً نقسم على هذا العدد الأولي ونكرر هذه الخطوات حتى نصل إلى 1.
  • يتم كل هذا في وقت O(log(n)) complexity، وتحسين كفاءة الحل كثيرا.
  • مما يجعل من الممكن حساب العوامل الأولية لأعداد أكبر بكثير من تلك التي كان من الممكن أن نتعامل معها باستخدام الطريقة السابقة.

على سبيل المثال:

الطريقة الثانية هي التحقق مما إذا كان يمكن كتابة الرقم بالشكل 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]

العوامل الأولية في بايثون باستخدام التكرار

هنا، سوف نكون شوwing كود بلغة بايثون للعثور على العوامل الأولية لعدد معين بطريقة تكرارية:

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

العوامل الأولية في بايثون باستخدام العودية

يعرض هذا القسم رمزًا في لغة بايثون استخدام طريقة الغربلة لإيجاد العوامل الأولية لعدد معين.

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 باستخدام التكرار

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