이 섹션에서는 효율적인 방법으로 숫자의 모든 소인수를 얻는 방법을 살펴보겠습니다. n =1092라는 숫자가 있습니다. 우리는 이것의 모든 소인수를 얻어야 합니다. 1092의 소인수는 2, 2, 3, 7, 13입니다. 이 문제를 해결하려면 다음 규칙을 따라야 합니다.
-
숫자가 2의 배수일 때 2를 출력하고, 숫자를 2로 반복해서 나눕니다.
-
이제 숫자는 홀수여야 합니다. 이제 숫자의 3부터 제곱근까지 숫자가 현재 값으로 나누어 떨어지면 인쇄하고 현재 숫자로 나누어 숫자를 변경한 다음 계속합니다.
더 나은 아이디어를 얻기 위해 알고리즘을 살펴보겠습니다.
알고리즘
printPrimeFactors(n)
begin while n is divisible by 2, do print 2 n := n / 2 done for i := 3 to √𝑛, increase i by 2, do while n is divisible by i, do print i n := n / i done done if n > 2, then print n end if end
예시
#include<stdio.h> #include<math.h> void primeFactors(int n) { int i; while(n % 2 == 0) { printf("%d, ", 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) { printf("%d, ", i); n = n/i; } } if(n > 2) { printf("%d, ", n); } } main() { int n; printf("Enter a number: "); scanf("%d", &n); primeFactors(n); }
출력
Enter a number: 24024 2, 2, 2, 3, 7, 11, 13,