숫자의 고유한 소인수의 곱을 찾는 C/C++ 프로그램?

이 섹션에서는 숫자의 고유한 소인수를 효율적으로 곱하는 방법을 살펴보겠습니다. n =1092라는 숫자가 있습니다. 우리는 이것의 고유한 소인수의 곱을 얻어야 합니다. 1092의 소인수는 2, 2, 3, 7, 13입니다. 따라서 고유 소인수는 {2, 3, 7, 13}이고 곱은 546입니다. 이 문제를 해결하려면 다음 규칙을 따라야 합니다 -

• 숫자가 2의 배수일 때 2에 곱을 곱하고 숫자를 2로 반복해서 나누면 다음 2는 무시됩니다.

• 이제 숫자가 홀수여야 합니다. 이제 숫자의 3부터 제곱근까지 숫자가 현재 값으로 나누어지면 인수를 곱하고 현재 숫자로 나누어 숫자를 변경한 다음 계속합니다. 다음은 위와 같이 무시됩니다.

• 그리고 마지막으로 숫자가 2보다 크면 1이 아니므로 나머지 숫자를 곱합니다.

더 나은 아이디어를 얻기 위해 알고리즘을 살펴보겠습니다.

알고리즘

고유한 프라임 제품(n)

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

예시

#include<stdio.h>
#include<math.h>
int uniquePrimeProduct(int n){
   int i, prod = 1;
   if(n % 2 == 0){
      prod *= 2;
      n = n/2;
   }
   while(n % 2 == 0){//skip next 2s
      n = n/2;
   }
   for(i = 3; i <= sqrt(n); i=i+2){ //i will increase by 2, to get only odd numbers
      if(n % i == 0){
         prod *= i;
         n = n/i;
      }
      while(n % i == 0){ //skip next i's
         n = n/i;
      }
   }
   if(n < 2){
      prod *= n;
   }
   return prod;
}
main() {
   int n;
   printf("Enter a number: ");
   scanf("%d", &n);
   printf("Product of prime factors: %d", uniquePrimeProduct(n));
}

출력

Enter a number: 1092
Product of prime factors: 546