อัลกอริธึมปัจจัยเฉพาะ: C, Python ตัวอย่าง

การแยกตัวประกอบเฉพาะคืออะไร?

ปัจจัยเฉพาะของที่กำหนด ใด number คือตัวประกอบที่เป็น a จำนวนเฉพาะ- ตัวประกอบเมื่อคูณจะได้ตัวเลขอีกจำนวนหนึ่ง จำนวนเฉพาะหารด้วยตัวมันเองหรือ 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)

Output:

Enter the number you want: 4
4

Python ปัจจัยสำคัญที่ใช้การเรียกซ้ำ

ส่วนนี้จะแสดงรหัสใน Python language โดยใช้วิธีตะแกรงหาตัวประกอบเฉพาะของจำนวนที่กำหนด

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)

Output:

Enter the number you want: 4
2
2

โปรแกรม C Prime Factors โดยใช้การวนซ้ำ

มันเป็นวิธีแก้ปัญหาเดียวกับ Python แบบวนซ้ำ แต่เขียนไว้ ภาษาซี.

เราขอให้ผู้ใช้กรอกตัวเลข จากนั้นสำหรับแต่ละตัวเลขตั้งแต่ 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;
}

Output:

Enter the number you want: 2
2

โปรแกรม C Prime Factors โดยใช้การเรียกซ้ำ

นี่เป็นวิธีแก้ปัญหาแบบเดียวกับ Python แบบเรียกซ้ำ แต่เขียนด้วยภาษา 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;
}

Output:

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 ไม่ใช่จำนวนเฉพาะหรือจำนวนประกอบ
• การแยกตัวประกอบเฉพาะของตัวเลขสามารถช่วยแก้ปัญหาต่างๆ เช่น การหาร การทำให้เศษส่วนง่ายขึ้น และการหาตัวส่วนร่วมของเศษส่วนต่างๆ
• นอกจากนี้ การใช้การแยกตัวประกอบเฉพาะที่น่าตื่นเต้นอย่างหนึ่งคือการทำลายรหัสลับที่เป็นตัวเลข