โปรแกรม C หาตัวประกอบเฉพาะที่ใหญ่ที่สุดของตัวเลข?

ในส่วนนี้ เราจะมาดูกันว่าเราจะหาตัวประกอบเฉพาะที่ใหญ่ที่สุดของจำนวนอย่างมีประสิทธิภาพได้อย่างไร มีตัวเลขบอกว่า n =1092 เราต้องได้ตัวประกอบเฉพาะที่ใหญ่ที่สุดของสิ่งนี้ ตัวประกอบเฉพาะของ 1092 คือ 2, 2, 3, 7, 13 ตัวประกอบที่ใหญ่ที่สุดคือ 13 ในการแก้ปัญหานี้ เราต้องปฏิบัติตามกฎนี้ -

• เมื่อตัวเลขหารด้วย 2 ลงตัว ให้เก็บ 2 เป็นจำนวนที่มากที่สุด และหารจำนวนด้วย 2 ซ้ำๆ

• ตอนนี้ตัวเลขต้องเป็นเลขคี่ ตอนนี้เริ่มจาก 3 ถึงรากที่สองของตัวเลข หากตัวเลขหารด้วยค่าปัจจุบันได้ลงตัว ให้เก็บตัวประกอบให้มากที่สุด แล้วเปลี่ยนตัวเลขโดยหารด้วยตัวเลขปัจจุบันแล้วดำเนินการต่อ

• และสุดท้ายหากจำนวนมากกว่า 2 ก็จะไม่ใช่ 1 ดังนั้นจงหาตัวประกอบเฉพาะสูงสุด

ให้เราดูอัลกอริธึมเพื่อความเข้าใจที่ดีขึ้น

อัลกอริทึม

getMaxPrimeFactors(n)

begin
   while n is divisible by 2, do
      max := 2
   n := n / 2
   done
   for i := 3 to √𝑛, increase i by 2, do
      while n is divisible by i, do
         max := i
         n := n / i
      done
   done
   if n > 2, then
      max := n
   end if
end

ตัวอย่าง

#include<stdio.h>
#include<math.h>
int getMaxPrimeFactor(int n) {
   int i, max = -1;
   while(n % 2 == 0) {
      max = 2;
      n = n/2; //reduce n by dividing this by 2
   }
   for(i = 3; i <= sqrt(n); i=i+2){ //i will increase by 2, to get
      only odd numbers
      while(n % i == 0) {
         max = i;
         n = n/i;
      }
   }
   if(n > 2) {
      max = n;
   }
   return max;
}
main() {
   int n;
   printf("Enter a number: ");
   scanf("%d", &n);
   printf("Max prime factor: %d", getMaxPrimeFactor(n));
}

ผลลัพธ์

Enter a number: 24024
Max prime factor: 13